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
// Jan Burdzicki
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	vector <int> liczby(n);

	map <int, int> mapka;

	for(int i = 0; i < n; i++)
	{
		cin >> liczby[i];

		mapka[liczby[i]]++;
	}

	vector <pair <int, int>> wartosci(mapka.begin(), mapka.end());

	string odpowiedzi(n, 'N');

	int rozmiar = (int) wartosci.size();

	if(rozmiar > 1)
	{
		long long suma_prefiksowa = 0;

		int max_wartosc = wartosci[rozmiar - 1].first;

		int min_wartosc = max_wartosc;

		bool ok = false;

		suma_prefiksowa += 1LL * wartosci[0].first * wartosci[0].second;

		for(int i = 1; i + 1 < rozmiar; i++)
		{
			int wartosc = wartosci[i].first;
			int ilosc = wartosci[i].second;

			if(!ok)
			{
				min_wartosc = wartosc;

				ok = true;
			}

			suma_prefiksowa += 1LL * wartosc * ilosc;

			if(suma_prefiksowa <= wartosci[i + 1].first)
			{
				min_wartosc = max_wartosc;

				ok = false;
			}
		}

		for(int i = 0; i < n; i++)
		{
			if(liczby[i] >= min_wartosc)
			{
				odpowiedzi[i] = 'T';
			}
		}
	}

	cout << odpowiedzi << "\n";
	return 0;
}