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
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>

using namespace std;

int main() {

    int catfishNum;
    scanf("%d\n", &catfishNum);

    vector<pair<long long, int> > weights(catfishNum);
    for (int i = 0; i < catfishNum; i++) {
        int weight;
        scanf("%d", &weight);
        pair<long long, int> indexedWeight(weight, i);
        weights[i] = indexedWeight;
    }

    sort(weights.begin(), weights.end());

    vector<long long> weightSums(catfishNum, 0);
    long long partialSum = 0;
    for (int i = 0; i < catfishNum; i++) {
        partialSum += weights[i].first;
        weightSums[i] = partialSum;
    }

    vector<bool> canBeKing(catfishNum, false);

    long long lightest = weights[0].first;
    int firstNotLightest = 0;
    for (; firstNotLightest < catfishNum && weights[firstNotLightest].first == lightest; firstNotLightest++) {
    }

    if (firstNotLightest < catfishNum) {
        canBeKing[weights[catfishNum - 1].second] = true;

        for (int i = catfishNum - 2; i >= firstNotLightest && weightSums[i] > weights[i + 1].first; i--) {
            canBeKing[weights[i].second] = true;
        }
    }

    for (int i = 0; i < catfishNum; i++) {
        if (canBeKing[i]) {
            printf("T");
        } else {
            printf("N");
        }
    }
    printf("\n");


    return 0;
}