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

struct Catfish {
    long long mass;
    int number;
};

bool operator<(const Catfish& lhs, const Catfish& rhs) {
    return lhs.mass > rhs.mass;
}

void solve_dataset();
std::vector<Catfish> read_catfish(std::istream& stream, const int count);
std::vector<bool> get_possible_kings(const std::vector<Catfish>& catfish);
std::vector<long long> get_suffix_mass_sums(
    const std::vector<Catfish>& catfish
);
void print_answers(std::ostream& stream, const std::vector<bool>& answers);

int main() {
    std::ios_base::sync_with_stdio(false);
    solve_dataset();
    return 0;
}

void solve_dataset() {
    int catfish_count;
    std::cin >> catfish_count;
    auto catfish = read_catfish(std::cin, catfish_count);
    std::sort(catfish.begin(), catfish.end());
    const auto can_be_king = get_possible_kings(catfish);
    print_answers(std::cout, can_be_king);
}

std::vector<Catfish> read_catfish(std::istream& stream, const int count) {
    std::vector<Catfish> catfish(count);
    for(int i = 0; i < count; i++) {
        stream >> catfish[i].mass;
        catfish[i].number = i;
    }
    return catfish;
}

std::vector<bool> get_possible_kings(const std::vector<Catfish>& catfish) {
    std::vector<bool> can_be_king(catfish.size(), false);
    const auto lightest = catfish.back().mass;
    const auto suffix_sums = get_suffix_mass_sums(catfish);
    for(int i = 0; i < static_cast<int>(catfish.size()); i++) {
        const auto& current = catfish[i];
        if(current.mass == lightest)
            continue;
        if(i == 0) {
            can_be_king[current.number] = true;
            continue;
        }
        const auto mass_after_eating_smaller = current.mass + suffix_sums[i];
        const auto& previous = catfish[i - 1];
        can_be_king[current.number] = mass_after_eating_smaller > previous.mass
            && can_be_king[previous.number];
    }
    return can_be_king;
}

std::vector<long long> get_suffix_mass_sums(
    const std::vector<Catfish>& catfish
) {
    std::vector<long long> sums(catfish.size(), 0);
    for(int i = static_cast<int>(sums.size()) - 2; i >= 0; i--)
        sums[i] = sums[i + 1] + catfish[i + 1].mass;
    return sums;
}

void print_answers(std::ostream& stream, const std::vector<bool>& answers) {
    for(const bool answer : answers)
        stream << (answer ? "T" : "N");
    stream << std::endl;
}