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
#include <iostream>
#include <set>
#include <vector>
#include <stack>

using namespace std;

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

    unsigned long long int n, m, k, r, c, z;
    unsigned long long int x = 0;

    unsigned long long int a, b, coord;


    cin >> n >> m >> k;

    set<unsigned long long> strongholds;
    set<unsigned long long> visited;
    set<unsigned long long> path;
    stack<unsigned long long> path_stack;

    unsigned long long max_coord = n * m;
    unsigned long long path_length = n + m - 1;
    unsigned long long curr;

    for (int i = 0; i < k; ++i) {
        cin >> r >> c >> z;

        a = (r ^ x) % n;
        b = (c ^ x) % m;
        coord = a + n * b;

        auto it = path.find(coord);
        if (it != path.end() || path.empty()) {
            // new stronghold is on the current path or there is no path
            visited.clear();
            path.clear();

            visited.insert(0);
            path_stack.push(0);

            while (!path_stack.empty()) {
                curr = path_stack.top();
                visited.insert(curr);
                if (                // try right

                        (curr + n) < max_coord // not on the bottom edge
                        && curr + n != coord // not hitting new stronghold
                        && (strongholds.find(curr + n)) == strongholds.end() // not hitting existing stronghold
                        && (visited.find(curr + n)) == visited.end() // not already visited
                        ) {
                    path_stack.push(curr + n);
                } else if ( // try down
                        (curr + 1) % n != 0 // not on the bottom edge
                        && curr + 1 != coord // not hitting new stronghold
                        && (strongholds.find(curr + 1)) == strongholds.end() // not hitting existing stronghold
                        && (visited.find(curr + 1)) == visited.end() // not already visited
                        ) {
                    path_stack.push(curr + 1);
                } else {
                    // there is no move
                    if (curr == max_coord - 1) {
                        while (!path_stack.empty()){
                            curr = path_stack.top();
                            path_stack.pop();
                            path.insert(curr);
                        }
                    } else {
                        path_stack.pop();
                    }
                }
            }

            if (path.size() != path_length) {
                // there is no path because of the new stronghold
                x = x ^ z;
                visited.clear();
                path.clear();
                cout << "TAK" << "\n";
            } else {
                // there is a path around new stronghold, add it to the list
                strongholds.insert(coord);
                cout << "NIE" << "\n";
            }
        } else {
            //stronghold is not on the current path, it can be safely added
            strongholds.insert(coord);
            cout << "NIE" << "\n";
        }

    }

    return 0;
}