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

using namespace std;

class Calc {
private:
    const int n;
    /** Tablica z danymi wejściowymi. Potrzebna, aby mieć kolejność danych na potrzeby wypisania wyniku */
    int* input=new int[n];
    /** Tablica, w której będą posortowane wpisy od najmniejszego */
    int* sorted=new int[n];
private:
    int minimal;
    int64_t sum;
public:
    Calc(int n): n(n), input(new int[n]), sorted(new int[n]) {
    }

    void read() {
        for(int i=0;i<n;++i) {
            int v;
            cin>>v;
            input[i]=sorted[i]=v;
        }
    }

    void prepare() {
        // Sortujemy według wielkości
        sort(sorted, sorted+n);
    }

    void process(int weight, int items) {
        const int64_t s=sum;
        sum+=(int64_t)weight*(int64_t)items;  // aktualizujemy sumę.

        if(s==0) {    // przerwa grupa wagowa
            minimal=weight+1;   // pierwsza grupa wagowa, nigdy nie może być finalną
            return;
        }

        if(s<=weight) {   // jeżeli suma wszystkich poprzednich jest mniejsza niż aktualna kategoria wagowa,
            // to znaczy, że minimalna waga jest przynajmniej rozmiaru tej grupy wagowej
            minimal=weight; // podnosimy poprzeczkę
        }
    }

    void calc() {
        minimal=0;
        sum=0;

        int weight=0;
        int weightStart=-1;

        for(int i=0;i<n;++i) {
            const auto v=sorted[i];
            if(weight==v) continue;   // pomijamy dla takich samych wag, bo liczymy jako całość (grupę wagową)
            if(weightStart>=0) {
                process(weight, i-weightStart );
            }

            weight=v;
            weightStart=i;
        }
        process(sorted[n-1], n-weightStart);    // ostatnia grupa wagowa

    }

    void print() {
        for(int i=0;i<n;++i) {
            cout<<((input[i]>=minimal)?'T':'N');
        }
        cout<<endl;
    }

};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Wczytujemy dane
    int n;
    cin>>n;

    Calc c(n);
    c.read();
    c.prepare();
    c.calc();
    c.print();

    return 0;
}