4268. [THUPC 2025 pre] 摊位分配

【题目描述】

T 大学拥有数不胜数的优秀社团，例如核心成员达到 118 人的酸协（Students' Association of Acid），刚成立就饱受关注的篹协（Students' Association of Bamboo Basket），当然还有名扬四海的蒜协（Students' Association of Garlic）。每学期伊始，T 大学都会统一举办全校性的社团招新活动。招新活动因规模庞大，故又被称为“百团大战”。如何把有限的场地像希尔伯特旅馆一般分配给各个社团，总是百团大战的负责人最头疼的问题。今年的负责人看中了蒜协将一整头大蒜干净利落地拆解成瓣的能力，因此找到了蒜协，希望可以用蒜法来解决分配摊位的问题。

具体而言，今年一共有 $T$ 个社团希望参加百团大战，而可供百团使用的场地可以看成沿着学堂路排成一条直线的 $H$ 个格子。为了鼓励社团之间的良性竞争，负责人决定根据每个社团上个学年对学校的贡献进行分配。按照提交参加申请的顺序，第 $i$ 个社团上个学年对 T 大学的贡献为 $u_i$。负责人希望根据以下规则将所有的 $H$ 个格子分配给每个社团：

• 对于每个社团，计算序列 $u_i, u_i/2, u_i/4, \cdots,u_i/2^{H-1}$；
• 对于计算得到的 $T\times H$ 个数值，每次从中删去一个最大的，并将一个格子分配给相应社团的摊位，直到所有 $H$ 个格子都分配完毕；如果出现多个最大值，
• 若有社团尚未分到格子，则优先分配给这样的社团，否则优先分配给原始的 $u_i$ 最大的社团；
• 如果仍有多个社团可以分配，则按提交参加申请的顺序分配。

因为蒜协大部分成员都去播种过冬的大蒜了，所以需要在烹饪和炼丹部打蒜蓉的你协助负责人计算一下每个社团能分到几个格子的摊位。

【输入格式】

输入的第一行包含一个两个正整数 $T(1\le T \le 10^5), H(1\le H \le 10^9)$，分别表示社团的数量和场地格子的数量。

输入的第二行包含 $T$ 个正整数 $u_1, u_2, \cdots,u_T(1\le u_i\le 10^9)$，分别表示每个社团的贡献。

【输出格式】

输出一行 $T$ 个整数，其中第 $i$（$1\le i\le T$） 个整数表示第 $i$ 个社团的摊位包括几个格子。

【样例输入 1】

4 7
2 1 4 3

【样例输出 1】

1 1 3 2

【样例输入 2】

9 27
801 919 210 101 417 713 304 613 921

【样例输出 2】

4 4 2 1 3 4 2 3 4

【来源】

清华大学学生算法协会 GitLink 仓库