PROG-1119: รัฐบาลผสม (coalition)

#include <bits/stdc++.h>

using namespace std;

long long cnt[300005],qs[300005];
long long n;
vector<pair<long long,long long> > plist;

int main(){
    scanf("%lld",&n);
    long long sum = 0;
    for(long long i=1;i<=n;i++){
        long long party;
        scanf("%lld",&party);
        plist.push_back({party,i});
        sum += party;
    }
    sum /= 2;
    sort(plist.begin(), plist.end());
    for(long long i=n;i>=1;i--){
        qs[i] = plist[i-1].first;
        qs[i] += qs[i+1];
    }
    long long cn = 1;
    for(auto c : plist){
        long long l = 1,r = n;
        long long num = c.first;
        long long ans = 0;
        while(l <= r){
            long long m = (l+r)/2;
            long long s = num + qs[m];
            if(m <= cn)
                s -= num;
            if(s > sum){
                ans = max(m,ans);
                l = m+1;
            }
            else
                r = m-1;
        }
        if(ans <= cn)
            cnt[c.second] = n-ans;
        else
            cnt[c.second] = n-ans+1;
        cn++;
    }
    for(long long i=1;i<=n;i++)
        printf("%lld\n",cnt[i]);
}