Canadian Computing Olympiad: 2016 Day 2, Problem 3

A group of ~N~ pirates found ~K~ gold coins. They must decide on a way to distribute the coins amongst themselves. They have agreed on the following rules:

The oldest pirate proposes a distribution. (You can assume that all the pirates' ages are distinct.) A distribution assigns a non-negative integer number of coins to each pirate such that the sum of these numbers equals ~K~.

Then, each pirate will vote either yes or no on the proposal. The number of yes votes required for the proposal to pass depends on the number of pirates. If there are ~X~ pirates, then ~V[X]~ yes votes are required for the proposal to pass. If the proposal passes, the coins are assigned according the proposed distribution and the process ends. Otherwise, the oldest pirate is thrown overboard and the process is repeated without him.

The pirates act according to the following rules. The rules are given in order of priority; for example, rule 2 is only applied to distinguish between multiple options that are optimal according to rule 1.

1. A pirate will act to prevent himself from being thrown overboard.
2. A pirate will act to maximize the number of coins he receives.
3. A pirate will act to maximize the number of pirates thrown overboard (excepting himself, because rule 1 takes priority).
4. A pirate will act to maximize the number of coins received by the oldest pirate. If there are still multiple choices that fit these rules, he will maximize the gold received by the second-oldest pirate, then the third-oldest pirate, etc.

If there are multiple options that are optimal according to these rules, then the pirate chooses an action arbitrarily. (You can assume that the answer to this problem does not depend on the pirate's choice in this case.) Additionally, all the pirates are perfectly logical and know all the information contained in this problem statement. They cannot form agreements or coalitions because they do not trust each other.

We will number the pirates from ~1~ to ~N~, where these are numbered from the youngest (pirate ~1~) to the oldest (pirate ~N~).

If there were only ~i~ pirates (where ~i = 1, \dots, N~), how many coins would the oldest of them get?

Input Specification

The first line of input will be the number ~N~ ~(2 \le N \le 10^6)~.

The second line of input will be the integer ~K~ ~(1 \le K \le 10^{18})~.

The next ~N~ lines of input contain ~V[i]~ ~(1 \le V[i] \le i)~ indicating the number of yes votes required for a proposal to pass if there are ~i~ pirates remaining ~(i = 1, \dots, N)~.

For 5 of the 25 available marks for this problem ~N \le 2\,000~.

For an additional 5 of the 25 available marks for this problem ~\max(1, i - 3) \le V[i] \le i~ for all ~i = 1, \dots, N~.

For an additional 5 of the 25 available marks for this problem, ~K = 10^{18}~.

Output Specification

The output should consist of ~N~ integers, printed one per line. The ~i^{th}~ line of output is the number of coins that the ~i^{th}~ pirate would get if they were the oldest pirate; in other words, if only pirates ~1, \dots, i~ existed. If the ~i^{th}~ pirate is thrown overboard, output -1 on the ~i^{th}~ line.

Sample Input 1

5
100
1
1
2
2
3

Sample Output 1

100
100
99
99
98

Explanation for Sample Output 1

If there are 2 pirates left, pirate 2 can propose that all of the gold coins go to him. Only 1 vote is required for this proposal to pass, so he can guarantee that it passes by voting for it.

If there are 3 pirates left, pirate 3 needs someone else to vote for his proposal. He can ensure this by giving 1 coin to pirate 1 and 99 to himself. Pirate 1 knows that if the proposal doesn't pass, he will receive nothing. So a single coin is enough to secure his vote.

If there are 4 pirates left, pirate 4 gives 1 gold coin to pirate 2 and 99 to himself.

If there are 5 pirates left, pirate 5 gives 1 gold coin to pirates 1 and 3 and keeps 98 coins for himself.

Sample Input 2

5
100
1
2
3
4
4

Sample Output 2

100
-1
-1
-1
100

Explanation for Sample Output 2

In this case, a full consensus is required for a proposal to pass, except when there are 5 pirates, in which case only 4 of the 5 votes are required.

If there is full consensus required, and there are 2 or more pirates, the youngest pirate will vote against the proposal to maximize their coins and also throw the most pirates overboard.

In the case where there are 5 pirates, the oldest pirate will propose to give himself 100 coins. Everyone except the youngest pirate will vote yes, because if this proposal doesn't pass, the youngest pirate will get all of them thrown overboard and then take the coins for himself when only he remains. Since the pirates don't want to be thrown overboard, they will vote yes, even though the oldest pirate will offer them nothing.

Sample Input 3

4
100
1
1
2
3

Sample Output 3

100
100
99
97

Explanation for Sample Output 3

The first three cases were explained in Sample Input 1. When there are 4 pirates, the oldest pirate needs 3 votes. He will give 2 coins to the youngest pirate and 1 coin to the second-youngest pirate, keeping the rest for himself.

Sample Input 4

4
2
1
1
2
3

Sample Output 4

2
2
1
-1

Explanation for Sample Output 4

The situation is the same as in Example 3, but now there are only 2 coins. With 1, 2 or 3 pirates, we have the same situations as in Example 3.

With 4 pirates, the oldest pirate does not have enough coins to ensure the 3 votes which he needs, so he will be thrown overboard.