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

using namespace std;

bool debug = false;

bool canEatNext(vector<pair<int, int>> &fish, vector<unsigned long long> &partialSum, int index)
{
    if (index == 0)
    {
        return (fish[index].first > fish[index + 1].first);
    }
    if ((partialSum[index - 1] / index) == fish[index].first)
        return false;
    if (index == fish.size() - 1)
        return true;
    return (partialSum[index - 1] + fish[index].first > fish[index + 1].first);
}

bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
}

int main()
{
    int n;
    cin >> n;

    vector<pair<int, int>> fish;
    fish.reserve(n);

    vector<unsigned long long> partialSum;
    partialSum.reserve(n);

    bool stillKing;

    for (int i = 0; i < n; i++)
    {
        int k;
        // filling the original array
        cin >> k;
        fish.push_back(make_pair(k, i)); // k = value, i = original index
    }

    sort(fish.begin(), fish.end());

    for (int i = 0; i < n; i++) {
        if (i == 0)
            partialSum[i] = fish[i].first;
        else
            partialSum[i] = partialSum[i - 1] + fish[i].first;
    }

    int breakingIndex = 0;

    for (int i = n -1; i >= 0; i--)
    {
        bool cont = canEatNext(fish, partialSum, i);
        if (debug) cout << i << ": " << " fish: " << fish[i].first << ", partialSum; " << partialSum[i] << ", continue? " << cont << endl;
        if (!cont)
        {
            breakingIndex = i;
            break;
        }
    }

    for (int i = 0; i < n; i++) {
        // cout << ((fish[i].second <= breakingIndex) ? 'T' : 'N');
        if (i <= breakingIndex) fish[i].first = 0; else fish[i].first = 1;
    }

    sort(fish.begin(), fish.end(), sortbysec);

    for (int i = 0; i < n; i++) {
        cout << ((fish[i].first == 0) ? 'N' : 'T');
    }

    // for (int i = 0; i < n; i++) {
    //     cout << ((fish[fish[i].second].first == 1) ? 'T' : 'N');
    // }

    // cout << i;

    // for (int i = 0; i < n; i++)
    // {
    //     cout << fish[i].first << " " << fish[i].second << endl;
    // }

    // sort(fish.begin(), fish.end());

    // cout << endl;

    // for (int i = 0; i < n; i++)
    // {
    //     cout << fish[i].first << " " << fish[i].second << endl;
    // }
}