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
/* 2021
 * Maciej Szeptuch
 */
#include <algorithm>
#include <cstdio>

unsigned int fish;
unsigned int weight[524288];
unsigned int order[524288];
long long unsigned int sum;

int main(void)
{
    scanf("%u", &fish);
    for(unsigned int f = 0; f < fish; ++f)
    {
        scanf("%u", &weight[f]);
        weight[f] *= 2;
        order[f] = f;
        sum += weight[f];
    }

    std::sort(order, order + fish, [&](const unsigned int a, const unsigned int b)
        { return weight[a] == weight[b] ? a < b : weight[a] > weight[b]; });

    unsigned int minKing = weight[order[0]] + 1;
    for(unsigned int f = 0, s = 0; f < fish && sum > 0; ++f)
    {
        for(; s < fish && weight[order[f]] == weight[order[s]]; ++s)
            sum -= weight[order[s]];

        if(sum > 0 && minKing < sum + weight[order[f]] * (s - f))
            minKing = weight[order[f]];
    }

    for(unsigned int f = 0; f < fish; ++f)
        putchar(weight[f] >= minKing ? 'T' : 'N');

    puts("");
    return 0;
}