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

using namespace std;

struct node {
    int index;
    int value;
    int sum;
    int nextEatenIndex;
    bool canBeKing;
};

int main()
{
    int n;
    scanf("%d", &n);
    vector<node> nodes(n);
    for(int i=0; i<n; i++) {
        nodes[i] = { i, 0, 0, -1, false };
        scanf("%d", &nodes[i].value);
    }
    
    sort(nodes.begin(), nodes.end(), [](node a, node b) { return a.value < b.value; });

    nodes[0].sum = nodes[0].value;
    int sum = nodes[0].sum;
    for(int i=1; i<nodes.size(); i++) {
        sum += nodes[i].value;
        nodes[i].sum = (nodes[i-1].value == nodes[i].value ? nodes[i-1].sum : sum);
    }
    
    int it = -1;
    for(int i=1; i<nodes.size(); i++) {
        if(nodes[i-1].sum == nodes[i].sum) {
            nodes[i].nextEatenIndex = nodes[i-1].nextEatenIndex;
            continue;
        }
        while(it + 1 < nodes.size() && nodes[it+1].value < nodes[i].sum) it++;
        nodes[i].nextEatenIndex = it;
    }

    for_each(nodes.begin(), nodes.end(), [&nodes](auto &node){
        int nextEatenIndex = node.nextEatenIndex;
        if(nextEatenIndex == -1) return;
        while(nodes[nextEatenIndex].nextEatenIndex > nextEatenIndex) nextEatenIndex = nodes[nextEatenIndex].nextEatenIndex;
        node.canBeKing = nextEatenIndex == nodes.size() - 1;
    });
    
    sort(nodes.begin(), nodes.end(), [](node a, node b) { return a.index < b.index; });

    for_each(nodes.begin(), nodes.end(), [](auto &node){
        printf("%c", node.canBeKing ? 'T' : 'N');
    });
    
    return 0;
}