题目背景

PA 2025 R4A.

$\textcolor{red}{\textbf{1G / 6s.}}$

题目描述

有 $n$ 名海盗，编号 $1\sim n$。海盗编号越小，他的地位越高。

每位海盗 $i$ 都有一个贪婪系数 $a_i$，为正整数。

他们获得了 $m$ 枚金币，现在要分金币。

分金币的方式如下：

• 船上编号最小的海盗提出一个分赃方案，即为每个船上的海盗 $i$ 分配 $b_i$ 枚金币。这里，$\sum b_i=m$。
• 然后，所有船上的海盗（包括提出方案的海盗）对该分赃方案投票，选择支持或反对。
  • 如果至少 $50\%$ 的海盗支持方案，则金币按照提议的方式分配。
  • 否则，提出方案的海盗被扔下船（他不再参与接下来的讨论，也无法获得任何金币）。随后，由仍在船上的编号最小的海盗重复上述过程，直到确定一种分配方式为止。

每个海盗 $i$ 选择支持该分赃方案，当且仅当，如果拒绝方案：

• 他最终会被扔下船（他提出自己的方案后会被否决）；

• 或者他在该方案中的收益 $b_i$ 满足 $b_i \geq d_i + a_i$，其中

  • $d_i$ 是当前方案被否决后，该海盗最终获得的金币数；
  • $a_i$ 是贪婪系数。

所有海盗都知道所有其他海盗的贪婪系数，每个人的策略都是固定的：

1. 如果提出方案的海盗无论如何都会被扔下船（不存在一个方案可接受）：
   • 该海盗提议自己独占所有金币，接受自己的命运，被扔下船。
2. 否则，存在至少一个可接受的方案。

   • 该海盗会选择提出其中一个方案（$0$ 金币也比被扔下船好）。

   • 在所有可接受的方案中，海盗会选择自己分得最多金币的方案；

   • 如果仍然有多个可接受方案，海盗更倾向于让编号较大的海盗获得更多金币。

     具体地说，编号为 $i$ 的海盗，在所有可接受方案中，最小化编号 $i+1$ 的海盗所获金币数。

     • 如果仍然有多个方案，则最小化编号 $i+2$ 的海盗所得金币数，依此类推。

求出最终每个海盗能够分得多少金币。

输入格式

第一行，两个正整数 $n,m$。

第二行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

• 若第 $i$ 个海盗被扔下船，$b_i=-1$；
• 否则 $b_i$ 为最终第 $i$ 个海盗分得的金币数。

3 100
28 1 56

44 0 56

5 1
1 1 1 1 1

-1 0 0 1 0

6 6
3 5 1 4 2 6

2 0 0 0 4 0

提示

样例解释

• 样例解释 $1$：

如果海盗 $1$ 被扔下船，那么海盗 $2$ 会独占所有金币（虽然海盗 $3$ 会投反对票，但是无济于事）。

因此，海盗 $1$ 无法说服海盗 $2$ 支持他的方案，除非他给海盗 $2$ 至少 $100 + 1 = 101$ 枚金币（这超出了总金币数）。

从而，海盗 $1$ 选择转而说服海盗 $3$，即给他足够多的金币，使他愿意支持该方案。海盗 $1$ 需要至少给海盗 $3$ $56$ 枚金币。

所以最终方案为：$b_1=44$，$b_2=0$，$b_3=56$。

在该方案下，海盗 $1,3$ 投下反对票，海盗 $2$ 无力回天。

• 样例解释 $2$：

对于海盗 $1$，金币无论如何都不够分，所以他被扔下船。

海盗 $2$ 有两个选择：

1. 将 $1$ 枚金币给海盗 $3$；
2. 将 $1$ 枚金币给海盗 $4$。

按照规则，他选择方案 $2$。

• 样例解释 $3$：海盗 $1,2,5$ 支持海盗 $1$ 的方案，所以方案成功通过。

数据范围

• $1 \leq n \leq 5\times 10^4$；
• $1 \leq m \leq 5\times 10^6$；
• $1\le a_i\le 64$。