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

using namespace std;

using int64 = long long;
struct Fish
{
    Fish(int64 _index=-1, int64 _weight=0){
        index = _index;
        weight = _weight;
    }
    int64 index{-1};
    bool canEatNext{false};
    bool canEatPrev{false};
    int64 prevSum{0};
    int64 weight{0};
    bool isKing{false};
};
void v1(){
    int64 n;
    cin >> n;
    std::vector<Fish> A(n);
    std::vector<int64> indexes(n, -1);
    for (int64 i=0;i<n;i++)
    {
        int64 a;
        cin >> a;
        A[i] = Fish{i, a};
    }
    std::sort(A.begin(), A.end(), [](const Fish& a, const Fish&b){
        return a.weight<b.weight;
    });

    indexes[A[0].index] = 0;
    for (int i=1;i<n;i++){
        indexes[A[i].index] = i;
        if (A[i].weight>A[i-1].weight){
            A[i].canEatPrev=true;
            A[i].prevSum = A[i-1].prevSum + A[i-1].weight;
            if (i<n-1){
                A[i].canEatNext = (A[i].prevSum + A[i].weight ) > A[i+1].weight;
            }
        }
        else
        {
            if (A[i-1].canEatPrev){
                A[i].canEatPrev=true;
                A[i].prevSum = A[i-1].prevSum + A[i-1].weight;
                if (i<n-1){
                    A[i].canEatNext = (A[i].prevSum + A[i].weight ) > A[i+1].weight;
                }
            }
        }
    }

    A[n-1].isKing = A[n-1].canEatPrev;
    for (int i=n-2; i>0;i--){
        if(A[i].canEatNext && A[i+1].isKing){
             A[i].isKing = true;
        }
    }

    for (int i=0;i<n;i++){
        int64 index = indexes[i];
        std::cout << (A[index].isKing ? "T" : "N");
    }
    std::cout << std::endl;
}

int main()
{
    v1();

    return 0;
}