#include <bits/stdc++.h> using namespace std; int n, t[500001], maks=0, wynik[500001], a, t2[500001], wyniki[500001]; int main() {std::ios_base::sync_with_stdio(0); cin>>n; for(int i=1; i<=n; i++){ cin>>a; t[i]=a; t2[i]=a; maks=max(maks, t[i]); //cout<<maks<<endl; } sort(t, t+n); /*for(int i=1; i<=n; i++){ cout<<t[i]; //maks=max(maks, t[i]); //cout<<maks<<endl; }*/ for(int i=n; i>0; i--){ wynik[i]=t[i]; for(int j=1; j<=n; j++){ if(i==j){ j++; } if(wynik[i]>maks){ //cout<<"T"<<"\n"; wyniki[t[i]]++; break; } if(wynik[i]>t[j]){ //cout<<i<<" "<<wynik[i]<<" "<<t[j]<<"\n"; wynik[i]+=t[j]; } if(wynik[i]<=t[j]){ //cout<<"N"<<"\n"; break; } } } for(int i=1; i<=n; i++){ if(wyniki[t2[i]]>0){ cout<<"T"; wyniki[t2[i]]--; } 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 | #include <bits/stdc++.h> using namespace std; int n, t[500001], maks=0, wynik[500001], a, t2[500001], wyniki[500001]; int main() {std::ios_base::sync_with_stdio(0); cin>>n; for(int i=1; i<=n; i++){ cin>>a; t[i]=a; t2[i]=a; maks=max(maks, t[i]); //cout<<maks<<endl; } sort(t, t+n); /*for(int i=1; i<=n; i++){ cout<<t[i]; //maks=max(maks, t[i]); //cout<<maks<<endl; }*/ for(int i=n; i>0; i--){ wynik[i]=t[i]; for(int j=1; j<=n; j++){ if(i==j){ j++; } if(wynik[i]>maks){ //cout<<"T"<<"\n"; wyniki[t[i]]++; break; } if(wynik[i]>t[j]){ //cout<<i<<" "<<wynik[i]<<" "<<t[j]<<"\n"; wynik[i]+=t[j]; } if(wynik[i]<=t[j]){ //cout<<"N"<<"\n"; break; } } } for(int i=1; i<=n; i++){ if(wyniki[t2[i]]>0){ cout<<"T"; wyniki[t2[i]]--; } else{ cout<<"N"; } } return 0; } |