103734: [Atcoder]ABC373 E - How to Win the Election

Problem Statement

An election is being held with $N$ candidates numbered $1, 2, \ldots, N$. There are $K$ votes, some of which have been counted so far.

Up until now, candidate $i$ has received $A_i$ votes.

After all ballots are counted, candidate $i$ $(1 \leq i \leq N)$ will be elected if and only if the number of candidates who have received more votes than them is less than $M$. There may be multiple candidates elected.

For each candidate, find the minimum number of additional votes they need from the remaining ballots to guarantee their victory regardless of how the other candidates receive votes.

Formally, solve the following problem for each $i = 1,2,\ldots,N$.

Determine if there is a non-negative integer $X$ not exceeding $K - \displaystyle{\sum_{i=1}^{N}} A_i$ satisfying the following condition. If it exists, find the minimum possible such integer.

• If candidate $i$ receives $X$ additional votes, then candidate $i$ will always be elected.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Let $C_i$ be the minimum number of additional votes candidate $i$ needs from the remaining ballots to guarantee their victory regardless of how other candidates receive votes. Print $C_1, C_2, \ldots, C_N$ separated by spaces.

If candidate $i$ has already secured their victory, then let $C_i = 0$. If candidate $i$ cannot secure their victory under any circumstances, then let $C_i = -1$.

Sample Input 1

5 2 16
3 1 4 1 5

Sample Output 1

2 -1 1 -1 0

$13$ votes have been counted so far, and $2$ votes are left.
The $C$ to output is $(2, -1, 1, -1, 0)$. For example:

• Candidate $1$ can secure their victory by obtaining $2$ more votes, while not by obtaining $1$ votes. Thus, $C_1 = 2$.
• Candidate $2$ can never (even if they obtain $2$ more votes) secure their victory, so $C_2 = -1$.

Sample Input 2

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

Sample Output 2

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

问题陈述

正在举行一场选举，有N名候选人，编号为1、2、…、N。共有K票，其中一些票已经被计算在内。

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

当所有选票都计算完毕后，候选人i（1≤i≤N）将会当选，当且仅当获得比他们多票的候选人数量少于M。可能会有多名候选人当选。

对于每位候选人，找出他们从剩余选票中至少需要获得的额外票数，以确保无论其他候选人如何获得票数，他们都能获胜。

正式地说，对于每个i=1,2,…,N，解决以下问题。

确定是否存在一个非负整数X，且X不超过K-Σ_{i=1}^{N} A_i，满足以下条件。如果存在，找出最小的这样的整数。

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

约束条件

• 1≤M≤N≤2×10^5
• 1≤K≤10^{12}
• 0≤A_i≤10^{12}
• Σ_{i=1}^{N} A_i≤K
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

N M K
A_1 A_2 … A_N

输出

设C_i是从剩余选票中候选人i至少需要获得的额外票数，以确保无论其他候选人如何获得票数，他们都能获胜。按空格分隔打印C_1, C_2, …, C_N。

如果候选人i已经确保了胜利，那么让C_i=0。如果候选人i在任何情况下都无法确保胜利，那么让C_i=-1。

示例输入1

5 2 16
3 1 4 1 5

示例输出1

2 -1 1 -1 0

到目前为止已经计算了13票，还剩下2票。
要输出的C是(2, -1, 1, -1, 0)。例如：

• 候选人1可以通过获得2张额外票数来确保胜利，而获得1张票则不行。因此，C_1=2。
• 候选人2即使获得2张额外票数也无法确保胜利，所以C_2=-1。

示例输入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