This is an exercise of binary search.

First of all, if \(N=M\) then all the candidates will win. From now on, we assume \(M<N\).

If one can solve the following decision problem, then the answer to this problem can be found with binary search:

if candidate \(i\) ends up obtaining a total of \(X\) votes, is it possible that each of the \(M\) candidates with most votes, except for candidate \(i\), has more than \(X\) votes?

If it is possible, then candidate \(i\) cannot secure their victory when they end up having \(X\) votes, as the result may not allow them to be elected. Conversely, if it is impossible, then candidate can always win if they obtain a total of \(X\) votes.

Consider how to solve this decision problem fast. For simplicity, we assume that \(A\) is sorted in ascending order.

We want to find at least how many additional votes are required for each of the \(M\) candidates with most votes, except for candidate \(i\), to have at least \((X+1)\) votes. For this count \(C\), the decision problem is answered “No” if \(C>K-\sum_{i=0}^N A_i\), and “Yes” otherwise.

We can assume that these \(M\) candidates are the \(M\) candidates with most votes counted so far, except for candidate \(i\), to find the minimum value. If \(1 \leq i \leq N-M\), then candidates \(N-M+1,\ldots ,N\) comprise the set, while when \(N-M+1 \leq i \leq N\), candidates \(N-M,N-M+1,\ldots,i-1,i+1,\ldots,N\) do. Now we need to find how many additional votes are required for each of these candidates to have at least \((X+1)\) votes.

Among these candidates, those with \((X+1)\) or more votes do not need additional votes, but those with \(j( \leq X)\) votes need \(X+1-j\) more votes. The sought value is found as the sum of this value, but naively finding it requires \(O(M)\) time to solve the decision problem, which is not fast enough.

To optimize it, we can use the properties that the top \(M\) candidates have mostly consecutive indices, and that whether they have \((X+1)\) or more votes or not is monotonic with respect to \(j\). They help us to utilize cumulative sums and binary search, enabling to find the value required to solve the decision problem. Specifically, do a binary search to find the maximum index of a candidate with \(X\) or less votes, find the number of candidates with that index or less, among those in the set we have defined above. The sought sum is (the number of candidates) \(\times (X+1)\), subtracted by the number of votes that those in the set have obtained so far. Finally, add the number of additional votes required for candidate \(i\) to end up having \(X\) or more votes to the sum, and the result is the minimum additional vote count required. Note that the \(M\) candidates in the set may not have fully consecutive indices, which requires additional caution in implementation. For more details, please refer to the sample code.

For each candidate, we perform this binary search \(O(\log K)\) times, and the decision problem can be solved in \(O(\log N)\) time. Hence, the problem can be solved in a total of \(O(N \log K \log N)\) time.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, m;
    ll k;
    cin >> n >> m >> k;
    vector<ll> a(n);
    for (auto& e : a) cin >> e;
    const ll rem = k - accumulate(a.begin(), a.end(), 0LL);

    if (n == m) {
        for (int i = 0; i < n; ++i) cout << 0 << " \n"[i == n - 1];
        return 0;
    }

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return a[i] < a[j]; });
    auto b = a;
    sort(b.begin(), b.end());
    vector<ll> sumb(n + 1);  // Cumulative sum of A sorted in ascending order
    for (int i = 0; i < n; ++i) sumb[i + 1] = sumb[i] + b[i];

    vector<ll> ans(n, -1);
    for (int i = 0; i < n; ++i) {
        ll l = -1, r = rem + 1;
        while (r - l > 1) {
            ll mid = (l + r) / 2;
            ll rid = lower_bound(b.begin(), b.end(), b[i] + mid + 1) - b.begin();  // Finds the maximum rid with b[rid]<b[i]+mid+1
            ll lid = n - m - (i >= n - m ? 1 : 0);  // If i < n-m, the top m candidates are n-m,...,n; if i >= n-m, the top m candidates are n-m-1,...,i-1,i+1,..,n.
            ll cnt = 0;
            if (rid > lid) cnt += (rid - lid) * (b[i] + mid + 1) - (sumb[rid] - sumb[lid]);
            if (lid <= i && i < rid)
                cnt--;  // In this case, candidate i already have b[i]+mid+1 votes, so decrement the count
            else
                cnt += mid;  // Add the number of votes that candidate i needs
            if (cnt > rem)
                r = mid;
            else
                l = mid;
        }
        if (l == rem)
            ans[ord[i]] = -1;
        else
            ans[ord[i]] = r;
    }

    for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n - 1];
}