#include <algorithm> #include <map> #include <set> #include <cstdio> #define ll long long using namespace std; int n; ll a[500005]; char res[500005]; void solve() { if(n == 1) { res[0] = 'T'; return; } map<ll, int> cm; ll mx = 0; for(int i=0;i<n;i++) { cm[a[i]]++; mx = max(mx, a[i]); } map<ll, ll> toS; ll total = 0; for(auto it = cm.begin();it!=cm.end();it++) { total += (it->first) * (it->second); toS[it->first] = total; if(total > mx) { break; } } set<ll> z; for(auto it = cm.begin();it!=cm.end();it++) { ll cur = it->first; ll eaten = 0; ll lastEat = -1; while(cur <= mx) { auto lo = toS.lower_bound(cur); if(lo == toS.begin()) { break; } lo--; if(lo->first <= lastEat) { break; } ll toEat = lo->second; lastEat = lo->first; if(lastEat >= it->first) { toEat -= it->first; } cur += toEat - eaten; eaten = toEat; } if(cur > mx) { z.insert(it->first); } } for(int i=0;i<n;i++) { res[i] = (z.find(a[i]) != z.end())?'T':'N'; } } int main(int argc, char** argv) { scanf("%d", &n); for(int i=0;i<n;i++) { scanf("%lld", &(a[i])); } solve(); res[n] = '\0'; printf("%s\n", res); 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 | #include <algorithm> #include <map> #include <set> #include <cstdio> #define ll long long using namespace std; int n; ll a[500005]; char res[500005]; void solve() { if(n == 1) { res[0] = 'T'; return; } map<ll, int> cm; ll mx = 0; for(int i=0;i<n;i++) { cm[a[i]]++; mx = max(mx, a[i]); } map<ll, ll> toS; ll total = 0; for(auto it = cm.begin();it!=cm.end();it++) { total += (it->first) * (it->second); toS[it->first] = total; if(total > mx) { break; } } set<ll> z; for(auto it = cm.begin();it!=cm.end();it++) { ll cur = it->first; ll eaten = 0; ll lastEat = -1; while(cur <= mx) { auto lo = toS.lower_bound(cur); if(lo == toS.begin()) { break; } lo--; if(lo->first <= lastEat) { break; } ll toEat = lo->second; lastEat = lo->first; if(lastEat >= it->first) { toEat -= it->first; } cur += toEat - eaten; eaten = toEat; } if(cur > mx) { z.insert(it->first); } } for(int i=0;i<n;i++) { res[i] = (z.find(a[i]) != z.end())?'T':'N'; } } int main(int argc, char** argv) { scanf("%d", &n); for(int i=0;i<n;i++) { scanf("%lld", &(a[i])); } solve(); res[n] = '\0'; printf("%s\n", res); return 0; } |