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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Sum {
    unsigned long w;
    int i;
    bool king;
};

int main() {
    int n; scanf("%d", &n);
    vector<Sum> weights(n);
    for (int i = 0; i < n; ++i) {
        unsigned long w;
        scanf("%lu", &w);
        weights[i] = {w, i, false};
    }

    sort(weights.begin(), weights.end(), [](const Sum& s1, const Sum& s2) {
        return s1.w < s2.w;
    });

    if (weights[0].w == weights[n-1].w) {
        for (int i = 0; i < n; ++i) printf("N");
        printf("\n");
        return 0;
    }

    vector<unsigned long> sums(n, 0);
    unsigned long s = 0;

    for (int i = 1; i < n; ) {
        if(weights[i].w != weights[i-1].w) {
            sums[i] = sums[i-1] + weights[i-1].w + s;
            s = 0;
            ++i;
        }
        else {
            while(i < n && weights[i].w == weights[i-1].w) {
                sums[i] = sums[i-1];
                s += weights[i-1].w;
                ++i;
            }
        }
    }

    // biggest sums:
    int i = n - 1;
    while(weights[i].w == weights[i-1].w) {
        weights[i].king = true;
        --i;
        
    }

    for (int j = i; j >= 0;) {
        if(sums[j] <= 0) break;

        // zjedz równe
        int k = j;
        int startw = sums[j];
        while (k >= 0 && weights[k].w == weights[k-1].w) {
            startw += weights[k-1].w;
            --k;
        }

        if(weights[j].w + startw > weights[j+1].w) {
            if(k == j) {
                weights[j].king = true;
                --j;
            }
            else {
                for (int l = j; l > k; --l) {
                    weights[l].king = true;
                }
                j = k;
            }
        }
        else {
            break;
        }
    }

    sort(weights.begin(), weights.end(), [](const Sum& s1, const Sum& s2) {
        return s1.i < s2.i;
    });

    for (int i = 0; i < n; ++i) {
        printf("%c", weights[i].king ? 'T' : 'N');
    }
    printf("\n");
    return 0;
}