P16012 [CCO 2016 Day 2] Pirates 海盗

一群 $N$ 个海盗发现了 $K$ 枚金币。他们必须决定如何分配这些金币。大家达成了以下规则： 年龄最大的海盗提出一个分配方案。（你可以假设所有海盗年龄都不同。）分配方案给每个海盗分配一个非负整数金币数，且这些金币数加起来正好是 $K$。 然后，每个海盗会对这个方案投赞成票（`yes`）或反对票（`no`）。方案通过所需的赞成票数取决于海盗人数。如果有 $X$ 个海盗，则需要 $V[X]$ 个 `yes` 票才能通过方案。如果方案通过，金币按照方案分配，过程结束。否则，年龄最大的海盗被扔下船，剩下的海盗重复这个过程。 海盗们的行为遵循以下规则。规则按优先级排列；比如规则 $2$ 只在规则 $1$ 无法区分多个最优选项时才用。 1. 海盗会尽力避免自己被扔下船。 2. 海盗会尽量让自己拿到更多金币。 3. 海盗会尽量让更多海盗被扔下船（除了自己，因为规则 $1$ 优先）。 4. 海盗会尽量让年龄最大的海盗拿到更多金币。如果还有多个选择符合以上规则，会依次让第二大、第三大海盗拿更多金币，以此类推。 如果多个方案在这些规则下都最优，海盗会随机选择一个。（你可以假设这不会影响最终答案。）此外，所有海盗都非常理性，且完全了解题目中的所有信息。他们不会结盟或合作，因为彼此不信任。 我们将海盗编号从 $1$ 到 $N$，编号从最年轻的海盗（$1$）到最年长的海盗（$N$）。 如果只有 $i$ 个海盗（其中 $i = 1, \dots, N$），那么最年长的海盗能拿到多少金币？

第一行输入一个数字 $N\ (2 \le N \le 10^6)$。 第二行输入一个整数 $K\ (1 \le K \le 10^{18})$。 接下来 $N$ 行，每行输入 $V[i]\ (1 \le V[i] \le i)$，表示当剩下 $i$ 个海盗时，方案通过所需的 `yes` 票数。 本题 $25$ 分中有 $5$ 分的测试点满足 $N \le 2\,000$。 另外 $5$ 分的测试点满足 $\max(1, i - 3) \le V[i] \le i$ 对所有 $i = 1, \dots, N$ 成立。 再有 $5$ 分的测试点满足 $K = 10^{18}$。

输出 $N$ 行整数。第 $i^{th}$ 行输出第 $i^{th}$ 个海盗如果是最年长海盗时能拿到的金币数；换句话说，如果只有 $1, \dots, i$ 个海盗存在时的结果。如果第 $i^{th}$ 个海盗被扔下船，则在第 $i^{th}$ 行输出 $-1$。

### 样例 $1$ 解释 当剩 $2$ 个海盗时，海盗 $2$ 可以提议把所有金币都给自己。只需 $1$ 票通过，他自己投赞成票，方案必定通过。 当剩 $3$ 个海盗时，海盗 $3$ 需要至少一个人支持他。他可以给海盗 $1$ 一枚金币，自己拿 $99$ 枚。海盗 $1$ 知道如果方案不通过，他将一文不名，所以给他一枚金币足够让他投赞成票。 当剩 $4$ 个海盗时，海盗 $4$ 给海盗 $2$ 一枚金币，自己拿 $99$ 枚。 当剩 $5$ 个海盗时，海盗 $5$ 给海盗 $1$ 和海盗 $3$ 各一枚金币，自己拿 $98$ 枚。 ### 样例 $2$ 解释 这次，除了 $5$ 个海盗时只需 $4$ 票通过外，其他情况都需要全票通过。 如果需要全票通过，且海盗数 $\ge2$，最年轻的海盗会投反对票，既能最大化自己的金币，也能让更多海盗被扔下船。 当有 $5$ 个海盗时，最年长的海盗会提议把 $100$ 金币全给自己。除了最年轻的海盗，其他人都会投赞成票，因为如果方案不通过，最年轻的海盗会把他们全部扔下船，自己独享金币。海盗们不想被扔下船，虽然没分到金币，还是投赞成票。 ### 样例 $3$ 解释 前三种情况在样例输入 $1$ 中已有解释。$4$ 个海盗时，最年长的海盗需要 $3$ 票通过。他会给最年轻的海盗 $2$ 枚金币，给第二年轻的海盗 $1$ 枚，自己拿剩下的金币。 ### 样例 $4$ 解释 情况和示例 $3$ 相同，但金币只有 $2$ 枚。$1$、$2$、$3$ 个海盗时情况和示例 $3$ 一样。 $4$ 个海盗时，最年长的海盗没有足够金币争取 $3$ 票通过，结果被扔下船。 翻译来源：GPT 4.1 mini。