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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#ifndef TS_DEBUG
#define NDEBUG
#endif

#ifdef _WIN32
#include <io.h>
#include <fcntl.h>
#endif

#include <assert.h>
#include <iostream>
#include <stdint.h>

typedef struct {
    int Stan;  // 0 - nic albo same 0, 1 - w pierwszym grafie, 2 - po pierszym grafie, 3 - NIE
    int Cin;
    int Cout;
    int Wy;
    int We;
} wyl_t;

wyl_t Wyl = {0};

void inicjuj()
{
    Wyl = {0};
}

void dodaj_zabawke_int(int NextA)
{
    if (Wyl.Stan == 3) return;

    if (NextA == 0 && (Wyl.Stan == 0 || Wyl.Stan == 2)) return;

    if (NextA == 0) {
        if (Wyl.We > 1 || (Wyl.We == 1 && Wyl.Cin > 0) ||
            Wyl.Wy > 1 || (Wyl.Wy == 1 && Wyl.Cout > 0)) {
                Wyl.Stan = 3;
                return;
            }
        Wyl.Stan = 2;
        return;
    }

    if (Wyl.Stan == 2) {
        Wyl.Stan = 3;
        return;
    }

    if (Wyl.We == NextA && Wyl.Wy == NextA) {
        if (Wyl.Cin == 0) {
            Wyl.We--;
            Wyl.Cin++;
        } else if (Wyl.Cout == 0) {
            Wyl.Wy--;
            Wyl.Cout++;
        } else {
            Wyl.Stan = 3;
            return;
        }
    }

    if (Wyl.We == NextA + 1 && Wyl.Cin == 0) {
        Wyl.We--;
        Wyl.Cin++;
    }

    if (Wyl.Wy == NextA + 1 && Wyl.Cout == 0) {
        Wyl.Wy--;
        Wyl.Cout++;
    }

    if (Wyl.We > NextA || Wyl.Wy > NextA) {
        Wyl.Stan = 3;
        return;
    }

    assert(Wyl.We <= NextA);
    assert(Wyl.Wy <= NextA);
    int NextWe = NextA - Wyl.Wy;
    int NextWy = NextA - Wyl.We;
    Wyl.We = NextWe;
    Wyl.Wy = NextWy;
    Wyl.Stan = 1;
}

void dodaj_zabawke(int NextA)
{
    //std::cerr << NextA << ":";
    dodaj_zabawke_int(NextA);
    //std::cerr << Wyl.Stan << ' ' << Wyl.Cin << ' ' << Wyl.Cout << ' ' << Wyl.Wy << ' ' << Wyl.We << std::endl;
}

bool sprawdz()
{
    dodaj_zabawke(0); // Żeby sprawdzić, czy graf jest zakończony
    return Wyl.Stan == 2;  // Był 1 graf i się zakończył
}

void sprawdz_plik(std::istream &Input, std::ostream &Output)
{
    int CntT = 0;
    int t;
    Input >> t;
    for (int i = 0; i < t; i++) {
        //std::cerr << "Case : " << (i + 1) << std::endl;
        int n;
        Input >> n;
        inicjuj();
        for (int j = 0; j < n; j++) {
            int a;
            Input >> a;
            dodaj_zabawke(a);
        }
        bool wynik = sprawdz();
        if (wynik) CntT++;
        Output << (wynik ? "TAK\n" : "NIE\n");
    }
    //std::cerr << "Actual   TAK: " << CntT << " NIE: " << (t - CntT) << " T: " << t << std::endl;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

#ifdef _WIN32
    _setmode( _fileno( stdout ),  _O_BINARY );
#endif

    sprawdz_plik(std::cin, std::cout);
    std::cout.flush();

    return 0;
}