AT_abc373_e [ABC373E] How to Win the Election

题目描述

现在正在举行一场选举，有 $N$ 位候选人，编号为 $1, 2, \ldots, N$。目前已经有 $K$ 张选票，其中一些已经被计入。

到目前为止，第 $i$ 位候选人已经获得了 $A_i$ 票。

在所有选票被计完后，如果某位候选人的得票数比他们多的候选人数少于 $M$，那么该候选人将被当选。可能会有多位候选人同时当选。

对于每个候选人，求出他们需要从剩余的选票中获得的最少票数，以确保无论其他候选人获得多少票，他们都能当选。

具体来说，对于每个 $i = 1, 2, \ldots, N$，解决以下问题：

确定是否存在一个非负整数 $X$，其不超过 $K - \displaystyle{\sum_{i=1}^{N}} A_i$，并满足以下条件。如果存在，找出满足条件的最小 $X$。

• 如果候选人 $i$ 获得了 $X$ 张额外选票，那么候选人 $i$ 将始终当选。

输入格式

第一行包含三个整数 $N$、$M$ 和 $K$。

第二行包含 $N$ 个整数，分别是 $A_1, A_2, \ldots, A_N$，表示每个候选人当前已经获得的票数。

输出格式

设 $C_i$ 为候选人 $i$ 从剩余选票中需要的最少额外票数，以保证无论其他候选人获得多少票，他们都能当选。输出 $C_1, C_2, \ldots, C_N$。

如果候选人 $i$ 已经确保当选，则 $C_i = 0$。如果候选人 $i$ 无法在任何情况下确保当选，则 $C_i = -1$。

输入输出样例 #1

输入 #1

5 2 16
3 1 4 1 5

输出 #1

2 -1 1 -1 0

输入输出样例 #2

输入 #2

12 1 570
81 62 17 5 5 86 15 7 79 26 6 28

输出 #2

79 89 111 117 117 74 112 116 80 107 117 106

说明/提示

• $1 \leq M \leq N \leq 2 \times 10^5$。
• $1 \leq K \leq 10^{12}$。
• $0 \leq A_i \leq 10^{12}$。
• $\displaystyle{\sum_{i=1}^{N} A_i} \leq K$。