//Jakub Rozek //Sumy //czas: n*log(n) //pamiec: n #include "bits/stdc++.h" using namespace std; const int N=500005; int n,x; pair <long long,int> t[N]; long long sum[N]; bool wyn[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1; i<=n; ++i) { cin>>x; t[i]={x,i}; } sort(t+1,t+1+n); for(int i=1; i<=n; ++i) { sum[i]=sum[i-1]+t[i].first; } if(t[n].first>t[1].first) wyn[t[n].second]=1; for(int i=n-1; i>=1; --i) { if(t[i].first>t[1].first && sum[i]>t[i+1].first) wyn[t[i].second]=wyn[t[i+1].second]; } for(int i=1; i<=n; ++i) { if(wyn[i]) 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 | //Jakub Rozek //Sumy //czas: n*log(n) //pamiec: n #include "bits/stdc++.h" using namespace std; const int N=500005; int n,x; pair <long long,int> t[N]; long long sum[N]; bool wyn[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1; i<=n; ++i) { cin>>x; t[i]={x,i}; } sort(t+1,t+1+n); for(int i=1; i<=n; ++i) { sum[i]=sum[i-1]+t[i].first; } if(t[n].first>t[1].first) wyn[t[n].second]=1; for(int i=n-1; i>=1; --i) { if(t[i].first>t[1].first && sum[i]>t[i+1].first) wyn[t[i].second]=wyn[t[i+1].second]; } for(int i=1; i<=n; ++i) { if(wyn[i]) cout<<"T"; else cout<<"N"; } return 0; } |