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 `#include using namespace std; typedef long long LL; int n, m, k, r, c, z, x; const LL M = 10000000; struct xxx{ LL ojciec; int ranga; }; map t; set s[100009]; set ::iterator it; void MakeSet(LL x){ t[x].ojciec=x; } LL Find(LL x){ if(t[x].ojciec == x) return t[x].ojciec; t[x].ojciec=Find(t[x].ojciec); return t[x].ojciec; } void Union(LL a, LL b){ LL fa=Find(a); LL fb=Find(b); if(fa==fb)return; if(t[fa].ranga>t[fb].ranga ){ t[fb].ojciec=t[fa].ojciec; t[fa].ranga++; } else{ t[fa].ojciec=t[fb].ojciec; t[fb].ranga++; } } bool check(){ r = (r^x)%n; c = (c^x)%m; LL tmp = M*r + c; MakeSet(tmp); LL gorne = -3; LL dolne = -4; if(r == 0 || c == m-1){ gorne = -1; } else{ if(!s[r-1].empty()){ it = s[r-1].lower_bound(c+1); if(*it > c+1 && it != s[r-1].begin() ){ --it; gorne = *it + (r-1)*M; } if(*it <= c+1) gorne = *it + (r-1)*M; if(it == s[r-1].end()) gorne = *s[r-1].rbegin() + (r-1)*M; } } if(r==n-1 || c == 0){ dolne = -2; } else{ if(!s[r+1].empty()){ it = s[r+1].lower_bound(c-1); if(*it >= c-1) dolne = *it + (r+1)*M; if(it == s[r+1].end()) dolne = -4; } } if(Find(gorne) == Find(-1) && Find(dolne) == Find(-2)){ x = x^z; return true; } if(gorne != -3){ Union(gorne, tmp); } if(dolne != -4){ Union(dolne, tmp); } s[r].insert(c); return false; } int main(){ scanf("%d%d%d", &n, &m, &k); MakeSet(-1); MakeSet(-2); MakeSet(-3); MakeSet(-4); for(int i=0; i