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

using namespace std;

unsigned int fishes[500000];
unsigned int sortedFishes[500000];

int main() {
    ios_base::sync_with_stdio(false);

    unsigned int fishCount;

    cin >> fishCount;

    for (unsigned int i = 0; i < fishCount; i++) {
        cin >> fishes[i];
        sortedFishes[i] = fishes[i];
    }

    sort(sortedFishes, sortedFishes + fishCount);

    unsigned int lastNotKingWeight = sortedFishes[0];
    long long int currentSum = 0;
    unsigned int currentIndex = 0;
    unsigned int previousWeight = sortedFishes[0];
    unsigned int currentWeight;

    while (currentIndex < fishCount) {
        currentWeight = sortedFishes[currentIndex];
        if (previousWeight != currentWeight && currentSum <= currentWeight) {
            lastNotKingWeight = previousWeight;
        }
        //cout << "currentIndex: " << currentIndex << ", previousWeight: "  << previousWeight << ", currentWeight: "  << currentWeight << ", currentSum: "  <<currentSum << ", lastNotKnightWeight: "  <<lastNotKingWeight << "\n";

        currentSum += currentWeight;
        previousWeight = currentWeight;
        currentIndex++;
    }

    for(unsigned int i = 0; i < fishCount; i++) {
        cout << (fishes[i] > lastNotKingWeight ? "T" : "N");
    }

    cout << "\n";

    return 0;
}