#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 500005; int tab[N]; int tab0[N]; bool symulacja(int a, int n){ ll masa = tab[a]; for(int i=0; i<n; ++i){ if(i==a) continue; if(masa > tab[i]){ masa += tab[i]; }else{ return false; } } return true; } int main(){ ios_base::sync_with_stdio(0); int n; cin >> n; for(int i=0; i<n; ++i){ cin >> tab0[i]; tab[i] = tab0[i]; } sort(tab,tab+n); int L=0,R=n-1,mid,best=-1; while(L<=R){ mid = (L+R)/2; if(symulacja(mid,n)){ R = mid - 1; best = mid; }else{ L = mid + 1; } } ll smallestKing; if(best < 0){ smallestKing = LONG_MAX; }else{ smallestKing = tab[best]; } for(int i=0; i<n; ++i){ if(tab0[i] >= smallestKing){ cout << 'T'; }else{ cout << 'N'; } } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 500005; int tab[N]; int tab0[N]; bool symulacja(int a, int n){ ll masa = tab[a]; for(int i=0; i<n; ++i){ if(i==a) continue; if(masa > tab[i]){ masa += tab[i]; }else{ return false; } } return true; } int main(){ ios_base::sync_with_stdio(0); int n; cin >> n; for(int i=0; i<n; ++i){ cin >> tab0[i]; tab[i] = tab0[i]; } sort(tab,tab+n); int L=0,R=n-1,mid,best=-1; while(L<=R){ mid = (L+R)/2; if(symulacja(mid,n)){ R = mid - 1; best = mid; }else{ L = mid + 1; } } ll smallestKing; if(best < 0){ smallestKing = LONG_MAX; }else{ smallestKing = tab[best]; } for(int i=0; i<n; ++i){ if(tab0[i] >= smallestKing){ cout << 'T'; }else{ cout << 'N'; } } return 0; } |