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
#include <stdio.h>
#include <vector>
#include <algorithm>


int main(){
	int n;
	scanf("%d",&n);
	std::vector<int> sumy(n);
	std::vector<int> sumyToSort(n);
	for(int i = 0; i < n; ++i){
		scanf("%d",&sumy[i]);
		sumyToSort[i] = sumy[i];
	}
	std::sort(sumyToSort.begin(), sumyToSort.end());
	long long int obecnaSuma = 0;
	long long int poprzedniaSuma = 0;
	long long int najwiekszyZablokowany = 0;
	if (sumyToSort[0] == sumyToSort.back()){
		najwiekszyZablokowany = sumyToSort[0];
	} else {
		for(int i = 0; i < n; ){
			int j = i;
			obecnaSuma = poprzedniaSuma;
//			printf("przed petla %d %d\n", i, j);
			while (j < n && sumyToSort[i] == sumyToSort[j]) {
//				printf("petla %d %d\n", i, j);
				obecnaSuma += sumyToSort[j];
				++j;
			}
			if (j == n || sumyToSort[i] < sumyToSort[j]) {//przypadek brzegowy
				--j;
			}

//			printf("%lld %d ---  %d %d\n", poprzedniaSuma, sumyToSort[i], i, j);
			long long int czynnikWzrostu = poprzedniaSuma == 0 ? 1 : (j - i  + 1);
			if (j < n - 1 && poprzedniaSuma  + sumyToSort[i] * czynnikWzrostu <= sumyToSort[j + 1]){
				najwiekszyZablokowany = sumyToSort[i];
//				printf("%lld === zablokowany\n",najwiekszyZablokowany);
			}

			poprzedniaSuma = obecnaSuma;

			i = j + 1;
		}
	}

	for(int i = 0 ; i < n; ++i){
		printf("%c", sumy[i] <= najwiekszyZablokowany ? 'N' : 'T');
	}
	printf("\n");
	return 0;
}