提出 #58222301

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long n, m, k, rem;
    cin >> n >> m >> k;
    rem = k;
    vector<long long> a(n), cum(n), ans(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        rem -= a[i];
    }

    vector<int> ind(n);
    iota(ind.begin(), ind.end(), 0);
    sort(ind.begin(), ind.end(), [&](int x, int y){return a[x] > a[y];});
    sort(a.begin(), a.end(), greater<long long>());

    auto sor = a;
    reverse(sor.begin(), sor.end());

    cum[0] = a[0];
    for(int i = 1; i < n; i++) cum[i] = cum[i-1] + a[i];

    for(int i = 0; i < n; i++){
        int in = ind[i];
        // cout << in << " " << a[i] << endl;
        long long lo = a[i], hi = rem + a[i], an = a[i]-1;
        while(hi >= lo){
            long long mid = (hi + lo) / 2;
            int pos = upper_bound(sor.begin(), sor.end(), mid) - sor.begin();
            pos = n - pos;
            if(pos >= m){
                lo = mid + 1;
                continue;
            }
            if(i < m){
                long long sum = cum[m] - (pos == 0? 0: cum[pos-1]);
                sum -= a[i];
                long long need = (mid + 1) * (m - pos) - sum;
                if(mid + need - a[i] <= rem){
                    lo = mid + 1;
                }
                else{
                    an = mid;
                    hi = mid - 1;
                }
            }
            else{
                long long sum = cum[m-1] - (pos == 0? 0: cum[pos-1]);
                long long need = (mid + 1) * (m - pos) - sum;
                if(mid + need - a[i] <= rem){
                    lo = mid + 1;
                }
                else{
                    an = mid;
                    hi = mid - 1;
                }
            }
        }
        ans[in] = an - a[i];
    }
    for(int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n-1]; 
}

提出情報

ジャッジ結果