1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ranges>
#include <vector>

int A[5000000];
int D[5000000];

struct Pirat
{
	int numer;
	int wymagania;

	bool operator<(const Pirat& p) const {
		return (wymagania < p.wymagania)
			|| (wymagania == p.wymagania && numer > p.numer);
	}
};

const int MAX_WYMAGANIA = 255;
int zliczenia_wymagan[MAX_WYMAGANIA+1];

void count_sort(const std::vector<Pirat>& piraci, std::vector<Pirat>& bufor) {
	memset(zliczenia_wymagan, 0, sizeof zliczenia_wymagan);

	for (const Pirat& pirat : piraci) {
		zliczenia_wymagan[pirat.wymagania-1]++;
	}
	for (int i=1; i<=MAX_WYMAGANIA; ++i) {
		zliczenia_wymagan[i] += zliczenia_wymagan[i-1];
	}

	bufor.resize(piraci.size());
	for (const Pirat& pirat : piraci) {
		bufor[--zliczenia_wymagan[pirat.wymagania-1]] = pirat;
	}
}

int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i=0; i<N; ++i) {
		scanf("%d", &A[i]);
	}

	std::vector<Pirat> lista_small, lista_temp;
	lista_small.reserve(N);
	lista_temp.reserve(N);

	for (int i=N-1; i>=0; --i) {
		// każdy z piratów przedstawia swój podział

		// trzeba sprawdzić, kogo z pozostałych musimy przekonać
		lista_temp.clear();
		size_t ilu_na_tak = 0;
		size_t ilu_glosujacych = 0;
		for (int j=i+1; j<N; ++j) {
			// dla każdego żywego pirata sprawdzamy ile dostanie
			// wg alternatywnego podziału d[i]
			// a my, żeby go przekonać, musimy zaproponować mu d[i]+a[i]
			// robimy listę piratów zaczynając od tych, których najłatwiej przekonać
			if (D[j] >= 0) {
				// tych z D[j]<0 nie musimy przekonywać, bo i tak zagłosują na TAK
				int wymagania = D[j] + A[j];
				if (wymagania <= MAX_WYMAGANIA) {
					lista_temp.push_back({ j, wymagania });
				}
				++ilu_glosujacych;
			} else {
				++ilu_na_tak;
			}
		}

		size_t ilu_potrzebujemy = (ilu_glosujacych+ilu_na_tak) / 2 - ilu_na_tak;

		count_sort(lista_temp, lista_small);

		lista_temp.clear();
		if (lista_small.size() < ilu_potrzebujemy) {
			// dodatkowo normalny sort, niestety
			for (int j=i+1; j<N; ++j) {
				if (D[j] >= 0) {
					// tych z D[j]<0 nie musimy przekonywać, bo i tak zagłosują na TAK
					int wymagania = D[j] + A[j];
					if (wymagania > MAX_WYMAGANIA) {
						lista_temp.push_back({ j, wymagania });
					}
				}
			}
			std::sort(lista_temp.begin(), lista_temp.end());
			lista_temp.resize(ilu_potrzebujemy - lista_small.size());
		} else {
			lista_small.resize(ilu_potrzebujemy);
		}

		int suma_łapówek = 0;
		for (const Pirat& pirat : lista_small) {
			suma_łapówek += pirat.wymagania;
			if (suma_łapówek > M) {
				break;
			}
		}
		if (suma_łapówek <= M) {
			for (const Pirat& pirat : lista_temp) {
				suma_łapówek += pirat.wymagania;
				if (suma_łapówek > M) {
					break;
				}
			}
		}
		if (suma_łapówek > M) {
			D[i] = -1; // wyskakuje za burtę, a podział pozostałych bez zmian
		} else {
			// jeśli doszliśmy już tutaj, to istnieje akceptowalny podział
			memset(D+i, 0, (N-i)*sizeof(int));
			for (const Pirat& pirat : lista_small) {
				D[pirat.numer] = pirat.wymagania;
			}
			for (const Pirat& pirat : lista_temp) {
				D[pirat.numer] = pirat.wymagania;
			}
			D[i] = M - suma_łapówek;
		}
	}

	printf("%d", D[0]);
	for (int j=1; j<N; ++j) {
		printf(" %d", D[j]);
	}
	putchar('\n');
}