P11924 [PA 2025] 贪婪大盗 / Piracka Chciwość

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$ 个海盗分得的金币数。

### 样例解释 - 样例解释 $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$。