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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
// #include <map>

using uint_ = unsigned int;
using ulong_ = unsigned long;

int main()
{
    // std::cout << 500000 << '\n';
    // for(int i=0; i<500000; ++i) {
    //     std::cout << i + 1'000'000'00 << " ";
    // }
    // std::cout << '\n';
    // return 0;

    std::size_t num_of_fish;
    std::cin >> num_of_fish;

    std::vector<uint_> input_order_sums;
    input_order_sums.reserve(num_of_fish);
    std::vector<std::tuple<ulong_, uint_, uint_>> prefix_sums;
    prefix_sums.reserve(num_of_fish);
    std::set<uint_> sums;
    std::unordered_map<uint_, std::pair<uint_, bool>> sum_counts;
    // std::map<uint_, std::pair<std::size_t, bool>> sum_counts;

    uint_ sum;
    auto n_cpy = num_of_fish;
    while(n_cpy--) {
        std::cin >> sum;
        input_order_sums.push_back(sum);
        sums.insert(sum);

        auto& [count, is_king] = sum_counts[sum];
        ++count;
        is_king = false;
    }

    //all are the same, noone is king
    if(sums.size() == 1) {
        for(std::size_t i=0; i<num_of_fish; ++i) {
            std::cout << "N";
        }
        std::cout << '\n';
        return 0;
    }

    bool is_first = true;
    ulong_ sum_of_sum = 0;
    std::size_t idx = 0;
    for(auto& s : sums) {
        sum_of_sum += static_cast<ulong_>(s) * static_cast<ulong_>(sum_counts[s].first);

        if(is_first) {
            prefix_sums.push_back({s, idx++, s});
            is_first = false;
            continue;
        }

        prefix_sums.push_back({sum_of_sum, idx++, s});
    }

    // for(auto& p : prefix_sums) {
    //     std::cout << std::get<0>(p) << " " << std::get<1>(p) << " " << std::get<2>(p) << '\n';
    // }

    // std::cout << '\n';

    auto cannot_be_king = [&](const std::tuple<ulong_, uint_, uint_>& sum_) {
        auto [sum, idx, s] = sum_;
        // ulong_ big_sum = sum;

        // std::cout << "sum: " << sum << " idx: " << idx << " id: " << s << '\n';

        //biggest fish can always become king
        if(idx == prefix_sums.size() - 1) {
            // std::cout << "biggest fish can always become king\n";
            // return true;
            return false;
        }

        // std::cout << sum <<  " > " << std::get<2>(prefix_sums[idx+1]) << '\n';
        while(idx+1 < prefix_sums.size() && sum > std::get<2>(prefix_sums[idx+1])) {
            sum += std::get<2>(prefix_sums[idx+1]);
            ++idx;
        }

        // std::cout << "idx == prefix_sums.size() - 1: " << (idx != (prefix_sums.size() - 1)) << "\n";
        return idx != prefix_sums.size() - 1;
    };

    //bin-search find first sum that can be king
    auto first_king = std::partition_point(prefix_sums.begin(), prefix_sums.end(), cannot_be_king);

    // for(idx = std::get<1>(*first_king); idx < prefix_sums.size(); ++idx) {
    for(auto it = first_king; it != prefix_sums.end(); ++it) {
        // auto fish_id = std::get<2>(prefix_sums[idx]);
        auto fish_id = std::get<2>(*it);

        sum_counts[fish_id].second = true;
    }

    // std::cout << std::get<1>(*first_king) << '\n';

    for(auto s : input_order_sums) {
        auto [count, is_king] = sum_counts[s];
        if(is_king) {
            std::cout << "T";
        } else {
            std::cout << "N";
        }
    }
    std::cout << '\n';

    return 0;
}