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
#include <stdio.h>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main(void) {
	size_t N; scanf("%lu", &N);
	pll *arr = new pll[N];
	for (size_t i=0; i<N; ++i) {
		scanf("%lli", &arr[i].first);
		arr[i].second = i;
	}
	sort(arr, arr+N);
	ll *prefix = new ll[N];

	bool all_same = false;
	size_t i = 0;
	do {
		prefix[i] = arr[i].first;
		++i;
	} while (arr[i].first == arr[i-1].first && i < N);
	if (i < N) { prefix[i] = i * arr[i-1].first + arr[i].first; ++i; }
	else all_same = true;

	for (; i < N; ++i) {
		prefix[i] = prefix[i-1] + arr[i].first;
	}

	bool *king = new bool[N];
	i = N-1;
	if (!all_same) king[i] = true; // todo: if not the same as the others
	for (--i; i != -1; --i) {
		if (prefix[i] > arr[i+1].first)
			king[i] = king[i+1];
		else
			king[i] = false;
	}

	// for (i = 0; i < N; ++i) {
	// 	printf("%lli ", arr[i].first);
	// }
	// puts("");
	// for (i = 0; i < N; ++i) {
	// 	printf("%lli ", prefix[i]);
	// }
	// puts("");
	// for (i = 0; i < N; ++i) {
	// 	printf("%lu ", king[i]);
	// }
	// puts("");
	// for (i = 0; i < N; ++i) {
	// 	printf("%c ", king[i] == N-1 ? 'T' : 'N');
	// }
	// puts("");

	pll *result = new pll[N];
	for (i = 0; i < N; ++i) {
		result[i] = { arr[i].second, king[i] };
	}
	sort(result, result+N);
	for (i = 0; i < N; ++i) {
		printf("%c", result[i].second ? 'T' : 'N');
	}
	puts("");

	return 0;
}