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
#include <iostream>
#include <cstdlib>

using namespace std;

typedef long ElementT;

ElementT a[500001], a_orig[500001], n, b[500001], b_nr, b_T1;
long long b_sum[500001];
//short b_TN[500001];

int sortuj(const ElementT *arg1, const ElementT *arg2)
{
    if ( *arg1 > *arg2 ) return 1;
    if ( *arg1 < *arg2 ) return -1;
    return 0;
}

int main()
{
    long i = 0;
    cin >> n;
    while (i < n) { cin >> a[i]; a_orig[i] = a[i]; i++;}
 
    qsort(a, n, sizeof(ElementT),( int( * )( const void *, const void * ) ) sortuj );

//    for (i = 0; i < n; i++) cout << a[i] << " "; cout <<endl;
    
    for (i = 0; i < n; i++) {
        if (b_nr == 0) {
            b_nr = 1; b[0] = a[i]; b_sum[0] = a[i];
        }
        else if (a[i] == b[b_nr - 1]) {
            b_sum[b_nr - 1] += a[i];
        }
        else {
            b_sum[b_nr] = b_sum[b_nr - 1] + a[i];
            b[b_nr++] = a[i];
        }
    }
    if (b_nr == 1) {
        i = 0;
        while (i++ < n) cout << 'N';
        return 0;
    }
    
    b_T1 = b_nr - 1;
    while (b_T1 > 1)
        if (b_sum[b_T1 - 1] > b[b_T1])
            b_T1--;
        else break;
        
//////    for (i = b_nr - 2; i > 0 ; i--) {
//////        if (b_sum[i] > b[i + 1]) b_TN[i] = 1;
//////    }

///**/    for (i = 0; i < b_nr; i++) cout << b[i] << " "; cout << endl;
///**/    for (i = 0; i < b_nr; i++) cout << b_sum[i] << " "; cout << endl;

///**/    i = 0; while (i < b_nr) cout << (b_TN[i++]?'T':'N'); cout << endl;

    long *p;
    for (i = 0; i < n; i++) {
/**/        p = (long *)bsearch(&(a[i]), b, b_nr, sizeof(ElementT), ( int( * )( const void *, const void * ) ) sortuj);
        p = (long *)bsearch(&(a_orig[i]), b, b_nr, sizeof(ElementT), ( int( * )( const void *, const void * ) ) sortuj);
        cout << (p - b >= b_T1 ? 'T' : 'N');
    }

    return 0;
}