#include <stdio.h> using ll=long long; const int C=500001, Inf = 1200000001; ll pom[C]; void Sebasort (ll tab[], int l, int r){ int lim=2, limi=l+1, limj=l+2, j=limi, i=l, k=l; while (lim/2<=r-l+1){ while (i<=r){ if (limj>r) limj=r+1; if ((j<limj&&tab[j]<tab[i])||i>=limi) pom[k]=tab[j], j++; else pom[k]=tab[i], i++; k++; if (i==limi&&j==limj) limi+=lim, limj+=lim, i=j, j=limi; } for (i=l;i<=r;i++) tab[i]=pom[i]; lim*=2, limi=l+lim/2, limj=l+lim, j=limi, i=k=l; } } ll a[C], b[C], summa[C]; int main(){ int i, n; ll v; scanf ("%d", &n); for (i=0; i<n; i++) scanf ("%lld", &a[i]), b[i]=a[i]; Sebasort(a, 0, n-1); summa[0]=a[0]; for (i=1; i<n; i++) summa[i] = summa[i-1]+a[i]; for (i=n-2; i>=0; i--){ if (a[i] == a[i+1]) continue; if (a[i]==a[0]) break; if (summa[i] <= a[i+1]) break; } i++; if (i<n && a[n-1]!=a[0]) v = a[i]; else v = Inf; for (i=0; i<n; i++){ if (b[i] >= v) printf ("T"); else printf ("N"); } printf ("\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 | #include <stdio.h> using ll=long long; const int C=500001, Inf = 1200000001; ll pom[C]; void Sebasort (ll tab[], int l, int r){ int lim=2, limi=l+1, limj=l+2, j=limi, i=l, k=l; while (lim/2<=r-l+1){ while (i<=r){ if (limj>r) limj=r+1; if ((j<limj&&tab[j]<tab[i])||i>=limi) pom[k]=tab[j], j++; else pom[k]=tab[i], i++; k++; if (i==limi&&j==limj) limi+=lim, limj+=lim, i=j, j=limi; } for (i=l;i<=r;i++) tab[i]=pom[i]; lim*=2, limi=l+lim/2, limj=l+lim, j=limi, i=k=l; } } ll a[C], b[C], summa[C]; int main(){ int i, n; ll v; scanf ("%d", &n); for (i=0; i<n; i++) scanf ("%lld", &a[i]), b[i]=a[i]; Sebasort(a, 0, n-1); summa[0]=a[0]; for (i=1; i<n; i++) summa[i] = summa[i-1]+a[i]; for (i=n-2; i>=0; i--){ if (a[i] == a[i+1]) continue; if (a[i]==a[0]) break; if (summa[i] <= a[i+1]) break; } i++; if (i<n && a[n-1]!=a[0]) v = a[i]; else v = Inf; for (i=0; i<n; i++){ if (b[i] >= v) printf ("T"); else printf ("N"); } printf ("\n"); return 0;} |