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
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define FORD(i, a, b) for (auto i=(a); i>(b); i--)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif

const int maxN = 1 << 16, maxA = 64;

int A[maxN], B[maxN];
std::vector <int> bidders[maxA + 2];

int getBidBucket(int i)
{
	return std::min(B[i], maxA+1);
}

void solve()
{
	int n, m, losersCnt = 0;
	scanf ("%d%d", &n, &m);
	FOR(i, 0, n)
		scanf ("%d", A+i), assert(A[i] <= maxA);
	FORD(i, n-1, -1)
	{
		int needed = (n-1-i) / 2, cost = 0, highBid = 0, agreedOnHB = -1;
		needed -= losersCnt;
		FORD(j, n-1, i)
			if (int b = getBidBucket(j); b != -1)
				bidders[b].push_back(j);
		assert(needed >= 0);
		FOR(bid, 0, maxA+1)
		{
			int agreed = std::min(needed, SZ(bidders[bid]));
			cost += agreed * bid;
			needed -= agreed;
			if (needed == 0)
			{
				highBid = bid;
				agreedOnHB = agreed;
				break;
			}
		}
		
		assert(agreedOnHB != -1);
		B[i] = cost <= m ? m - cost + A[i] : -1;
		bool success = B[i] != -1;
		losersCnt += not success;

		FOR(b, 0, highBid)
		{
			if (success)
				for (int j : bidders[b])
					B[j] += A[j];
			bidders[b].clear();
		}
		if (success) FOR(jt, 0, SZ(bidders[highBid]))
		{
			int j = bidders[highBid][jt];
			B[j] = jt < agreedOnHB ? B[j] + A[j] : A[j];
		}
		bidders[highBid].clear();
		FOR(b, highBid+1, maxA+2)
		{
			if (success)
				for (int j : bidders[b])
					B[j] = A[j];
			bidders[b].clear();		
		}
	}

	bool leaderOcc = false;
	FOR(i, 0, n)
	{
		if (B[i] != -1)
			leaderOcc = true, B[i] -= A[i];
		else if (leaderOcc)
			B[i] = 0;
		
		printf("%d ", B[i]);
	}
	printf("\n");
}

int main()
{
	int tc = 1;
//	scanf ("%d", &tc);	

	FOR(cid, 1, tc+1)
		solve();
	return 0;
}