#include <iostream> #include <algorithm> using namespace std; long long n, x, sumaprzed, sumapo, w, s[500005], p, ile; pair<int, int> t[500005]; bool b[500005], k; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i=0; i<n; ++i) { cin >> x; t[i].first=x; t[i].second=i; } sort(t,t+n); s[0]=t[0].first; p=t[0].first; b[t[0].second]=0; for(int i=1; i<n; ++i) { if(p==t[i].first) { ile++; b[t[i].second]=0; } s[i]=s[i-1]+t[i].first; } if(t[n-1].first!=p) { b[t[n-1].second]=1; for(int i=n-1; i>ile; --i) { if(s[i]>t[i+1].first) b[t[i].second]=1; else break; } } for(int i=0; i<n; ++i) { if(!b[i]) cout << "N"; else cout << "T"; } 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 | #include <iostream> #include <algorithm> using namespace std; long long n, x, sumaprzed, sumapo, w, s[500005], p, ile; pair<int, int> t[500005]; bool b[500005], k; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i=0; i<n; ++i) { cin >> x; t[i].first=x; t[i].second=i; } sort(t,t+n); s[0]=t[0].first; p=t[0].first; b[t[0].second]=0; for(int i=1; i<n; ++i) { if(p==t[i].first) { ile++; b[t[i].second]=0; } s[i]=s[i-1]+t[i].first; } if(t[n-1].first!=p) { b[t[n-1].second]=1; for(int i=n-1; i>ile; --i) { if(s[i]>t[i+1].first) b[t[i].second]=1; else break; } } for(int i=0; i<n; ++i) { if(!b[i]) cout << "N"; else cout << "T"; } return 0; } |