#include <iostream> #include <algorithm> using namespace std; long long int n, i, a; pair <long long int, long long int> s[500001]; long long int tab[500001]; bool wyniki[500001]; int main() { cin >> n; for(i=0;i<n;i++) { cin >> a; s[i]=make_pair(a, i); } sort(s, s+n); /*for(i=0;i<n;i++) { cout << s[i].first << " "<< s[i].second << endl; }*/ a=0; for(i=0;i<n;i++) { if(i==0) { a+=s[i].first; tab[i]=a; continue; } if(s[i].first>s[i-1].first) { a+=s[i].first; tab[i]=a; //cout << "es2134" << endl; } else { tab[i]=a; //cout << "jdjdjd334" << endl; } } wyniki[s[n-1].second]=true; /*cout << endl; cout << s[n-1].second << "s " << endl;*/ for(i=n-2;i>=0;i--) { //cout << tab[i] << " A " << s[i+1].first << endl; if(tab[i]>s[i+1].first) { wyniki[s[i].second]=true; } else { break; } } for(i=0;i<n;i++) { if(wyniki[i]==true) { cout << 'T'; } else { cout << 'N'; } } /*cout << endl; for(i=0;i<n;i++) { cout << tab[i] << " "; }*/ 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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include <iostream> #include <algorithm> using namespace std; long long int n, i, a; pair <long long int, long long int> s[500001]; long long int tab[500001]; bool wyniki[500001]; int main() { cin >> n; for(i=0;i<n;i++) { cin >> a; s[i]=make_pair(a, i); } sort(s, s+n); /*for(i=0;i<n;i++) { cout << s[i].first << " "<< s[i].second << endl; }*/ a=0; for(i=0;i<n;i++) { if(i==0) { a+=s[i].first; tab[i]=a; continue; } if(s[i].first>s[i-1].first) { a+=s[i].first; tab[i]=a; //cout << "es2134" << endl; } else { tab[i]=a; //cout << "jdjdjd334" << endl; } } wyniki[s[n-1].second]=true; /*cout << endl; cout << s[n-1].second << "s " << endl;*/ for(i=n-2;i>=0;i--) { //cout << tab[i] << " A " << s[i+1].first << endl; if(tab[i]>s[i+1].first) { wyniki[s[i].second]=true; } else { break; } } for(i=0;i<n;i++) { if(wyniki[i]==true) { cout << 'T'; } else { cout << 'N'; } } /*cout << endl; for(i=0;i<n;i++) { cout << tab[i] << " "; }*/ return 0; } |