PROG-T1119: Coalition

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

const int N = 3e5;

int qsum[N + 1], arr[N + 1];

int main(){

    int nTeams;
    scanf("%d", &nTeams);
    for(int i = 1; i <= nTeams; ++i){
        scanf("%d", &arr[i]);
        qsum[i] = arr[i];
    }
    sort(qsum + 1, qsum + nTeams + 1, greater<int>());
    for(int i = 1; i <= nTeams; ++i){
        qsum[i] += qsum[i - 1];
    }

    int tr = qsum[nTeams] / 2;
    int bigNumAns = upper_bound(qsum + 1, qsum + nTeams + 1, tr) - qsum;
    for(int i = 1; i <= nTeams; ++i){
        int idx = upper_bound(qsum + 1, qsum + nTeams + 1, tr - arr[i]) - qsum;
        if(qsum[idx] - qsum[idx - 1] <= arr[i]){
            cout << bigNumAns - 1 << '\n';
        } else {
            cout << idx << '\n';
        }
    }

    return 0;
}