해적

시간 제한10초메모리 제한512 MB

요약

해적 수가 1명에서부터 늘어날 때, 주어진 투표 규칙과 우선순위에 따라 가장 나이 많은 해적이 받는 금화 수를 각 경우에 대해 구한다.

난이도: 어려움10점 중 9점
유형: 그리디, 동적 계획법, 수학, 게임 이론
정답자: 아직 제출이 없습니다

문제

해적 $N$ 명이 금화 $K$ 개를 발견했다. 해적들은 금화를 나눠 가질 방법을 정해야 하며, 다음 규칙에 합의했다.

가장 나이 많은 해적이 분배안을 제안한다. (모든 해적의 나이는 서로 다르다고 가정해도 된다.) 분배안은 각 해적에게 음이 아닌 정수 개의 금화를 배정하며, 배정한 금화의 합은 $K$ 여야 한다.

그다음 모든 해적이 제안에 '찬성' 또는 '반대'로 투표한다. 제안이 통과하는 데 필요한 찬성 수는 남은 해적 수에 따라 다르다. 해적이 $X$ 명 남아 있으면 찬성이 $V[X]$ 표 이상 나와야 제안이 통과한다. 제안이 통과하면 제안대로 금화를 나누고 과정이 끝난다. 통과하지 못하면 가장 나이 많은 해적을 바다에 던지고, 그를 뺀 나머지 해적으로 과정을 반복한다.

해적은 아래 규칙에 따라 행동한다. 규칙은 우선순위 순서로 주어진다. 예를 들어 규칙 2는 규칙 1로 보아 똑같이 최선인 선택지가 여러 개일 때 그중에서 고르는 데에만 쓰인다.

해적은 자신이 바다에 던져지지 않도록 행동한다.
해적은 자신이 받는 금화 수를 최대화하도록 행동한다.
해적은 바다에 던져지는 해적 수를 최대화하도록 행동한다. (자신은 제외한다. 규칙 1이 우선하기 때문이다.)
해적은 가장 나이 많은 해적이 받는 금화 수를 최대화하도록 행동한다.

그래도 규칙에 맞는 선택지가 여러 개이면 두 번째로 나이 많은 해적이 받는 금화를 최대화하고, 그다음은 세 번째로 나이 많은 해적이 받는 금화를 최대화하는 식으로 이어진다. 이 규칙들로도 최선인 선택지가 여러 개이면 해적은 그중 아무것이나 고른다. (이때 해적이 무엇을 고르든 이 문제의 답은 달라지지 않는다고 가정해도 된다.) 또한 모든 해적은 완벽하게 논리적이며, 이 문제에 적힌 정보를 모두 알고 있다. 해적들은 서로 믿지 않으므로 약속을 하거나 편을 짤 수 없다.

해적에게는 가장 어린 해적(해적 1)부터 가장 나이 많은 해적(해적 $N$ )까지 1부터 $N$ 까지 번호가 붙어 있다.

각 $i = 1, \ldots, N$ 에 대해, 해적 1부터 $i$ 까지만 있다면 그중 가장 나이 많은 해적은 금화를 몇 개 받는지 구하시오.

입력

첫째 줄에 해적 수 $N$ 이 주어진다. ( $2 \le N \le 10^6$ )

둘째 줄에 금화 수 $K$ 가 주어진다. ( $1 \le K \le 10^{18}$ )

다음 $N$ 개의 줄에는 정수가 하나씩 주어진다. 그중 $i$ 번째 줄의 $V[i]$ 는 해적이 $i$ 명 남았을 때 제안이 통과하는 데 필요한 찬성 수이다. ( $1 \le V[i] \le i$ )

출력

정수 $N$ 개를 한 줄에 하나씩 출력한다. $i$ 번째 줄에는 해적 $i$ 가 가장 나이 많은 해적일 때, 즉 해적 1부터 $i$ 까지만 있을 때 해적 $i$ 가 받는 금화 수를 출력한다. 해적 $i$ 가 바다에 던져진다면 $i$ 번째 줄에 -1을 출력한다.

예제4

예제 1
입력
```
5
100
1
1
2
2
3
```
예상 출력
```
100
100
99
99
98
```
예제 2
입력
```
5
100
1
2
3
4
4
```
예상 출력
```
100
-1
-1
-1
100
```
예제 3
입력
```
4
100
1
1
2
3
```
예상 출력
```
100
100
99
97
```
예제 4
입력
```
4
2
1
1
2
3
```
예상 출력
```
2
2
1
-1
```