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
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
/*  Potyczki Algorytmiczne 2021 Runda 3 C Sumy (SUM)
    tsz
*/
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <memory.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

#include <algorithm>

#ifndef TSDEBUG
#define NDEBUG 1
#endif

#ifdef __MINGW32__
#define FMTU64 "I64u"
#define FMTI64 "I64d"
#else
#define FMTU64 "llu"
#define FMTI64 "lld"
#endif 

typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;

typedef uint64_t u64;

inline i32 Min(i32 a, i32 b)
{
    return a <= b ? a : b;
}

inline i32 Max(i32 a, i32 b)
{
    return a >= b ? a : b;
}

const i32 MinLiczbaSumow = 2;
const i32 MaxLiczbaSumow = 500000;
const i32 MaxWagaSuma = 1000000000;

i32 Sumy[MaxLiczbaSumow + 1] = { 0 };
i32 SumyPosortowane[MaxLiczbaSumow + 1] = { 0 };
i32 WagiSumow[MaxLiczbaSumow + 1] = { 0 };
i64 SumyWag[MaxLiczbaSumow + 1] = { 0 };

int main()
{
    i32 LiczbaSumow = 0;
    scanf("%d\n", &LiczbaSumow);
    assert(MinLiczbaSumow <= LiczbaSumow);
    assert(LiczbaSumow <= MaxLiczbaSumow);

    for (i32 i = 0; i < LiczbaSumow; i++) {
        i32 Sum;
        scanf("%d", &Sum);
        assert(1 <= Sum);
        assert(Sum <= MaxWagaSuma);
        Sumy[i] = Sum;
    }

    memmove(SumyPosortowane, Sumy, sizeof(Sumy[0]) * LiczbaSumow);
    std::sort(&SumyPosortowane[0], &SumyPosortowane[LiczbaSumow]);

    i32 OstatniSum = SumyPosortowane[0];
    i64 Suma = OstatniSum;
    i32 LiczbaWag = 0;
    //fprintf(stderr, "DEBUG: Liczba wag %d, suma %" FMTI64 ", ostatni %d\n", LiczbaWag, Suma, OstatniSum);
    for (i32 i = 1; i < LiczbaSumow; i++) {
        i32 Sum = SumyPosortowane[i];
        if (Sum != OstatniSum) {
            WagiSumow[LiczbaWag] = OstatniSum;
            SumyWag[LiczbaWag] = Suma;
            LiczbaWag++;
            OstatniSum = Sum;
        }
        Suma += Sum;
        //fprintf(stderr, "DEBUG: Liczba wag %d, suma %" FMTI64 ", ostatni %d\n", LiczbaWag, Suma, OstatniSum);
    }
    WagiSumow[LiczbaWag] = OstatniSum;
    SumyWag[LiczbaWag] = Suma;
    LiczbaWag++;
    //fprintf(stderr, "DEBUG: Liczba wag %d, suma %" FMTI64 ", ostatni %d\n", LiczbaWag, Suma, OstatniSum);

    if (LiczbaWag == 1) {
        for (i32 i = 0; i < LiczbaSumow; i++) {
            putchar('N');
        }
        putchar('\n');
        return 0;
    }

    i32 NajnizszyKandydat = WagiSumow[LiczbaWag-1];
    for (i32 i = LiczbaWag - 2; i >= 1; i--) {
        if (SumyWag[i] <= NajnizszyKandydat) {
            break;
        }
        NajnizszyKandydat = WagiSumow[i];
    }

    for (i32 i = 0; i < LiczbaSumow; i++) {
        putchar(Sumy[i] >= NajnizszyKandydat ? 'T' : 'N');
    }
    putchar('\n');

    return 0;
}