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

using namespace std;

constexpr int chunks = 675175;

int n;

size_t hashes[chunks];

std::hash<std::string> hash_fn;

using ull = unsigned long long;

int main() {
    scanf("%d\n", &n);

    if (n == 0) {
        std::string s;
        cin >> s;

        n = s.length();

        for (int i = 0; i <= n/2; ++i) {
            if (s[i] != s[n-i-1]) {
                printf("NIE\n");
                return 0;
            }
        }

        printf("TAK\n");
        return 0;
    }

    bool skip_middle = false;
    if (n % 2 == 1) {
        // skip middle
        skip_middle = true;
    }

    n /= 2;

    for (int ch = 0; ch < chunks; ++ch) {
//        printf("%d\n", ch);

        std::string s;
        int start = (int)(((ull)(ch) * (ull)(n))/((ull)chunks));
        int end   = (int)(((ull)(ch+1) * (ull)(n))/((ull)chunks));

//        printf("(%d %d)\n", start, end);
        for (int i = start; i < end; ++i) {
            char c;
            scanf("%c", &c);

            s += c;
        }

//        cout << "|" << s << "|" << endl;

        hashes[ch] = hash_fn(s);
    }

    if (skip_middle) {
        char c;
        scanf("%c", &c);
    }

    for (int ch = chunks-1; ch >= 0; --ch) {
//        printf("%d\n", ch);

        std::string s;
        int start = (int)(((ull)(ch) * (ull)(n))/((ull)chunks));
        int end   = (int)(((ull)(ch+1) * (ull)(n))/((ull)chunks));
        for (int i = start; i < end; ++i) {
            char c;
            scanf("%c", &c);

            s += c;
        }

        std::reverse(s.begin(), s.end());

//        cout << "|" << s << "|" << hashes[ch] << " " << hash_fn(s) << endl;

        if (hashes[ch] != hash_fn(s)) {
            printf("NIE\n");
            return 0;
        }
    }

    printf("TAK\n");
    return 0;
}