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
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <set>
#include <cmath>
#include <string>
#include <map>
#include <cassert>
#include <functional>
#include <tuple>

using namespace std;

struct Catfish {
    int position;
    int weight;
    bool possible_king;
    Catfish(int w, int p): weight(w), position(p) {}
};

int n, lowest_possible_king;
long long sum;
vector<Catfish> v;

bool cmp_weight(Catfish a, Catfish b){
    return a.weight < b.weight;
}

bool cmp_position(Catfish a, Catfish b){
    return a.position < b.position;
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i){    
        int a;
        scanf("%d", &a);
        v.push_back(Catfish(a, i));
    }
    sort(v.begin(), v.end(), cmp_weight);

    for (int i=0; i<n; ++i){
        v[i].possible_king = ( (sum + v[i].weight) > ((i+1<n)? v[i+1].weight : 0) );
        sum += v[i].weight;
    }
    // mark lowest weight as not possible kings
    for (int i=0; i<n && v[i].weight == v[0].weight; ++i){
        v[i].possible_king = false;
    }
    // find the gap between possible kings and the rest
    for (int i=n-1; i>=0 && v[i].possible_king; --i){
        lowest_possible_king = v[i].weight;
    }

    sort(v.begin(), v.end(), cmp_position);

    for (int i=0; i<n; ++i){
        printf("%c", ( v[i].possible_king && v[i].weight >= lowest_possible_king )? 'T' : 'N');
    }
    return 0;
}