/ 
Time Limit: 2.5 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1,2,\ldots,N の番号のついた N 人の候補者で選挙が行われています。K 票の投票があり、現在一部の開票作業が行なわれました。
これまでの開票作業では、i 番目の候補者に A_i 票が入りました。
全ての票が開票された後、i 番目 (1 \leq i \leq N) の候補者はその候補者より多く票を獲得した候補者が M 人未満であるとき、かつその時に限り当選します。複数の候補者が当選することもあります。
各候補者が当選を確定させるためには残りの票のうち最小で何票追加で票が必要か求めてください。
より厳密には、i = 1,2,\ldots,N に対して次の問題を解いてください。
次の条件を満たす K - \displaystyle{\sum_{i=1}^{N}} A_i 以下の非負整数 X が存在するか判定し、存在するならその最小値を求めてください。
- これ以降の開票作業で i 番目の候補者へ X 票入るなら、i 番目の候補者は必ず当選する。
制約
- 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
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 \ldots A_N
出力
候補者 i が当選を確定させるために必要な票数を C_i としたとき、C_1,C_2,\ldots,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
すでに 14 票の開票が終了しており、残りの票数は 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
Score : 500 points
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
14 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 more vote. 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