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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;


int main() {
    std::ios::sync_with_stdio(false);
    int n, x;
    cin >> n;
    vector<int> fish;
    for(int i = 0; i < n; ++i) {
        cin >> x;
        fish.push_back(x);
    }

    vector<int> original_fish = fish;
    sort(fish.begin(), fish.end());
    int max_fish = fish.back() + 1;
    vector<int> sums = {fish[0]};
    for(int i = 1; i < n; ++i) {
        sums.push_back(min(fish[i] + sums[i - 1], max_fish));
        if(fish[i] > fish[i - 1]) {
            int haps = sums[i], ii = i;
            for(int j = i + 1; j < n; ++j) {
                if(haps > fish[j]) {
                    sums.push_back(min(fish[j] + sums[j - 1], max_fish));
                    haps = min(haps + fish[j], max_fish);
                } else {
                    i = j - 1;
                    break;
                }
            }

            if(haps > fish.back()) {
                max_fish = fish[ii];
                break;
            }
        }
    }
    vector<char> res;
    for(auto &s: original_fish) {
        if(s >= max_fish) {
            res.push_back('T');
        } else {
            res.push_back('N');
        }
    }
    string outp(res.begin(), res.end());
    cout << outp << endl;
}