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

using integ = int_fast64_t;

struct Catfish {
    integ weight{0};
    integ sumStrictlySmaller{0};
    bool canBeKing{false};
};

int main() {
    std::size_t n;

    std::cin >> n;

    std::vector<Catfish> catfish(n);
    for(auto && fish : catfish) {
        std::cin >> fish.weight;
    }

    // Get indices sorted by catfish weight
    std::vector<integ> growingWeightInds(n);
    std::iota(growingWeightInds.begin(), growingWeightInds.end(), 0);
    const auto catfishIndCompar = [&catfish](integ lhs, integ rhs) {
        return catfish[lhs].weight > catfish[rhs].weight;
    };
    std::sort(growingWeightInds.begin(), growingWeightInds.end(), catfishIndCompar);

    // For each fish get the sum of smaller fish it can eat
    integ same = 1;
    for(integ i = n - 2; i >= 0; --i) {
        auto ind = growingWeightInds[i];
        auto indNext = growingWeightInds[i + 1];
        // The next fish is smaller or equal, so this one can eat at least what the next one could
        catfish[ind].sumStrictlySmaller = catfish[indNext].sumStrictlySmaller;
        // In addition it could possibly eat thee next one and all its peers...
        if(catfish[ind].weight + catfish[ind].sumStrictlySmaller > catfish[indNext].weight) {
            // ...this one can eat it in addition
            catfish[ind].sumStrictlySmaller += same * catfish[indNext].weight;
            same = 1;
        } else if(catfish[ind].weight == catfish[indNext].weight) {
            ++same;
        }
    }

    // Can any catfish become the king
    auto ind = growingWeightInds[0];
    auto indNext = growingWeightInds[1];
    if(catfish[ind].weight + catfish[ind].sumStrictlySmaller > catfish[indNext].weight){
        catfish[ind].canBeKing = true;
        for(integ i = 1; i < n; ++i) {
            auto ind = growingWeightInds[i];
            auto indPrev = growingWeightInds[i - 1];
            // Can the current fish eat the (possibly) bigger one after eating all the smaller ones
            if(catfish[ind].weight + catfish[ind].sumStrictlySmaller > catfish[indPrev].weight) {
                catfish[ind].canBeKing = true;
            }
            // The first time this is not possible marks the point after which no fish can become the king
            else {
                break;
            }
        }
    }

    // Print the result
    for(auto &&fish : catfish) {
        std::cout << (fish.canBeKing ? 'T' : 'N');
    }
    std::cout << std::endl;

    return 0;
}