#include <iostream> #include <algorithm> using namespace std; #define FORE(x, b, e) for(int x = b; x <= (e); ++x) #define FORL(x, b, e) for(int x = b; x < (e); ++x) #define P(x) cout <<#x <<'=' <<(x) <<" "; #define PP cout <<endl; #define Pv(x,a,b) cout << #x<<'=';for(int i=a;i<=b;i++)cout<<' '<<x[i];PP #define Pvv(x,y,a,b) cout <<#x <<#y <<'=';FORE(i,a,b)cout<<' '<<x[y[i]];PP typedef long long INT; #define MAX 500000 int ryby[MAX+2], klasa[MAX+2], idx[MAX+2]; INT csum[MAX+2]; char odp[MAX+2]; int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m=0; cin >>n; int x,X=0; FORE(i,1,n) { cin >>x; if(x>X) X=x; ryby[i] = x; odp[i] = 'T'; idx[i] = i; } x=n+1; ryby[x] = X+1; idx[x] = n+1; odp[x] = 0; INT Ryba = X; std::sort(idx, idx+n+2, [](int i, int j){ return ryby[i] < ryby[j]; }); csum[0] = X = 0; FORE(i,1,n) { x = ryby[idx[i]]; if(x!=X) { m++; klasa[m] = X = x; csum[m] = csum[m-1]; } csum[m] += x; if(m==1) odp[idx[i]] = 'N'; } for(int i=m-1;i>1;i--) { if(csum[i]<=klasa[i+1]) { x=klasa[i]; int j=0,k; while(ryby[k=idx[++j]]<=x) odp[k]='N'; break; } } cout << odp+1 <<'\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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include <iostream> #include <algorithm> using namespace std; #define FORE(x, b, e) for(int x = b; x <= (e); ++x) #define FORL(x, b, e) for(int x = b; x < (e); ++x) #define P(x) cout <<#x <<'=' <<(x) <<" "; #define PP cout <<endl; #define Pv(x,a,b) cout << #x<<'=';for(int i=a;i<=b;i++)cout<<' '<<x[i];PP #define Pvv(x,y,a,b) cout <<#x <<#y <<'=';FORE(i,a,b)cout<<' '<<x[y[i]];PP typedef long long INT; #define MAX 500000 int ryby[MAX+2], klasa[MAX+2], idx[MAX+2]; INT csum[MAX+2]; char odp[MAX+2]; int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m=0; cin >>n; int x,X=0; FORE(i,1,n) { cin >>x; if(x>X) X=x; ryby[i] = x; odp[i] = 'T'; idx[i] = i; } x=n+1; ryby[x] = X+1; idx[x] = n+1; odp[x] = 0; INT Ryba = X; std::sort(idx, idx+n+2, [](int i, int j){ return ryby[i] < ryby[j]; }); csum[0] = X = 0; FORE(i,1,n) { x = ryby[idx[i]]; if(x!=X) { m++; klasa[m] = X = x; csum[m] = csum[m-1]; } csum[m] += x; if(m==1) odp[idx[i]] = 'N'; } for(int i=m-1;i>1;i--) { if(csum[i]<=klasa[i+1]) { x=klasa[i]; int j=0,k; while(ryby[k=idx[++j]]<=x) odp[k]='N'; break; } } cout << odp+1 <<'\n'; return 0; } |