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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <cstdio>
#include <algorithm>
using namespace std;

struct Sum{
    int pozycja;
    unsigned int waga;
    int jakosc;
    //int zjedzone;
}sum[500005];
int n;

bool odNajmniejszego(Sum a, Sum b){
    return a.waga < b.waga;
}

bool kolejne(Sum a, Sum b){
    return a.pozycja < b.pozycja;
}

void wyswietl(const char *str){
    printf("%s\n",str);
    for(int i=0; i<n; i++){
        printf("%d - i:%d q:%d\n",sum[i].waga,sum[i].pozycja,sum[i].jakosc);
    }
    printf("\n");
    return;
}
int main(){
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        scanf("%d",&sum[i].waga);
        sum[i].pozycja = i;
        sum[i].jakosc = 0;
        //sum[i].zjedzone = 0;
    }
    sort(sum, sum+n, odNajmniejszego);
    //wyswietl("Najmniejsze");

    int suma=0; //najwiekszy zbior najmniejszych sumow do polkniecia
    int prestiz=0;//aktualny prestiz - najbardziej prestizowym gatunkiem sa wszystkie sumy o najwyzszej jakosci
    bool zjadaNajwiekszego = false; //osiagniecie mozliwosci zjedzenia wszystkich ryb
    //ustawianie pierwszego karpia
    suma += sum[0].waga;
    int i=1;
    //zliczaj wszystkie najmniejsze karpie niezdolne do polkniecia kogokolwiek
    while(i<n && sum[i].waga == sum[i-1].waga){
        suma += sum[i].waga;
        i++;
        //printf("!");
    }
    //no to jesli jest chociaz jeden wiekszy w akwenie to sa przynajmniej jacys pretendenci do nagrody Krola Karpia
    if(i<n)
        prestiz++;

    if(prestiz == 0){
        while(n-->0){
            printf("N");
        }
        printf("\n");
        return 0;
    }

    for(; i<n-1; i++){
        if(zjadaNajwiekszego){
            sum[i].jakosc = prestiz;
//          printf("^: %d\n",i);
            continue;
        }
        if(sum[i].waga + suma > sum[i+1].waga){
            sum[i].jakosc = prestiz;
            suma += sum[i].waga;
            if(suma > sum[n-1].waga)
                zjadaNajwiekszego = true;
//          printf("+: %d\n",i);
            continue;
        }
        sum[i].jakosc = prestiz;
        suma += sum[i].waga;
        prestiz++;
//      printf("-: %d\n",i);

    }

    //sprawdz najwiekszego karpia czy to boss nad bossy
    if(!zjadaNajwiekszego && sum[n-2].waga + suma < sum[n-1].waga){
        prestiz++;
        suma += sum[i].waga;
//        printf("Latest Biggest+: %d\n",i);
    }
    sum[n-1].jakosc = prestiz;

    sort(sum, sum+n, kolejne);

//  wyswietl("Kolejne");
    for(int i=0; i<n; i++){
        if(sum[i].jakosc == prestiz)
            printf("T");
        else
            printf("N");
    }
    printf("\n");

    return 0;
}