#include<bits/stdc++.h> using namespace std; #define d(a)cout<<#a<<" = "<<a<<"\n"; #define f first #define s second #define mp make_pair #define TURBO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define MAXN 500500 ll a[MAXN]; ll b[MAXN]; ll sum[MAXN]; map<ll,ll>eq; int main(){ TURBO; int n; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; b[i]=a[i]; eq[a[i]]++; } sort(a,a+n); ll cur=a[0]; for(int i=1;i<n;i++){ sum[i]=sum[i-1]; if(a[i]>a[i-1]){ sum[i]+=cur; cur=0; } cur+=a[i]; } a[n]=a[n-1]; ll minSUM=(1LL<<30LL); for(int i=n-1;i>=0;i--){ if(a[i]+sum[i]+((sum[i]>0)*(eq[a[i]]-1)*a[i])>a[i+1])minSUM=a[i]; else break; } for(int i=0;i<n;i++)if(b[i]>=minSUM)cout<<"T";else cout<<"N"; }
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 | #include<bits/stdc++.h> using namespace std; #define d(a)cout<<#a<<" = "<<a<<"\n"; #define f first #define s second #define mp make_pair #define TURBO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long #define MAXN 500500 ll a[MAXN]; ll b[MAXN]; ll sum[MAXN]; map<ll,ll>eq; int main(){ TURBO; int n; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; b[i]=a[i]; eq[a[i]]++; } sort(a,a+n); ll cur=a[0]; for(int i=1;i<n;i++){ sum[i]=sum[i-1]; if(a[i]>a[i-1]){ sum[i]+=cur; cur=0; } cur+=a[i]; } a[n]=a[n-1]; ll minSUM=(1LL<<30LL); for(int i=n-1;i>=0;i--){ if(a[i]+sum[i]+((sum[i]>0)*(eq[a[i]]-1)*a[i])>a[i+1])minSUM=a[i]; else break; } for(int i=0;i<n;i++)if(b[i]>=minSUM)cout<<"T";else cout<<"N"; } |