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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, i, t;
	unsigned long long suma = 0;
	map<int, vector<int>, greater<int>> xd;
	cin >> n;
	for(i=0; i<n; ++i) {
		cin >> t;
		xd[t].push_back(i);
		suma += t;
	}
	string wynik(n, 'N'	);
	if(xd.size()<2) {
		cout << wynik << '\n';
		return 0;
	}
	for(auto &&e : xd.begin()->second) // największe wygrywają z miejsca
		wynik[e] = 'T';
	suma -= xd.begin()->first*xd.begin()->second.size(); // wywalamy największe ryby
	for(auto pit = xd.begin(), it = next(xd.begin(), 1); it!=xd.end(); ++pit, ++it) {
		// zakładamy, że pit może wygrać cały; teraz pytanie czy ity mogą zjeść pity
		// cerr << suma << ' ' << it->first << ' ' << pit->first << endl;
		if(it->first==xd.rbegin()->first||suma<=pit->first) break; // nie
		for(auto &&e : it->second) // tak
			wynik[e] = 'T';
		suma -= it->first * it->second.size();
	}
	cout << wynik << '\n';
	return 0;
}