include iostream include vector include algorithm using namespace std

  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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
int m, n, d;
struct v2 {
int x, y;
v2(int x_, int y_): x(x_), y(y_) {}
double fi() const { return atan2(y, x); }
};
inline bool operator < (const v2 _v1, const v2 _v2) { return _v1.fi() < _v2.fi(); }
typedef unsigned int uint;
inline vector<uint> mult(vector<uint> l, vector<uint> r){
vector<uint> ans(4, 0);
ans[0] = l[0] * r[0] + l[1] * r[2];
ans[1] = l[0] * r[1] + l[1] * r[3];
ans[2] = l[2] * r[0] + l[3] * r[2];
ans[3] = l[2] * r[1] + l[3] * r[3];
return ans;
}
inline vector<uint> binpow(vector<uint> a, int n){
vector<uint> ans(4, 0);
ans[0] = ans[2] = 1;
while (n){
if (n & 1) ans = mult(ans, a);
a = mult(a, a);
n >>= 1;
}
return ans;
}
uint s0;
inline uint gets(int i, int j) {
int a = i * n + j + 1;
vector<uint> ar (4, 0);
ar[0] = 1664525;
ar[1] = 1013904223;
ar[3] = 1;
ar = binpow(ar, a);
return (ar[0] * s0 + ar[1]) % 3;
}
vector<v2> v2s;
const double pi = 2 * acos(0);
const double fieps = pi / 10;
const pair<int, int> undef = mp(-1, -1);
void init(int d) {
for(int x = -d; x <= d; x++) {
for(int y = -d; y <= d; y++) {
int R2 = sqrt(x*x + y*y);
if(R2 > d) continue;
v2s.pb(v2(x, y));
}
}
sort(all(v2s));
}
inline int sqr(int a) {
return a * a;
}
inline int dist2(int i1, int j1, int i2, int j2) {
return sqr(i1 - i2) + sqr(j1 - j2);
}
int main() {
cin >>m >>n >>d >>s0;
int d2 = sqr(d);
int i = 0, j = 0;
while(dist2(i, j, m - 1, n - 1) > d2) {
cout <<i + 1 <<" " <<j + 1 <<endl;
double curfi = atan2(n - j, m - i);
uint sij = gets(i, j);
bool found = false;
for(auto it = lower_bound(all(v2s), v2(cos(curfi - fieps) * 10000, sin(curfi - fieps) * 10000)); it != v2s.end() && it->fi() < curfi - fieps; it++) {
int i_ = i + it->x, j_ = j + it->y;
if(gets(i_, j_) == (sij + 1) % 3) {
i = i_, j = j_;
found = true;
break;
}
}
if(!found) {
cout <<"ERROR POINT NOT FOUND!" <<endl;
exit(1);
}
}
uint stateDist = (1LL * gets(m - 1, n - 1) - gets(i, j) + 3) % 3;
if(stateDist == 0) {
uint s1 = (1LL * gets(i, j) + 1) % 3;
pair<int, int> p1 = undef, p2 = undef;
uint s2 = (1LL * gets(i, j) + 2) % 3;
for(int x = i; x < m; x++) {
for(int y = j; y < n; y++) {
if(p1 != undef && gets(x, y) == s1) p1 = mp(x, y);
if(p2 != undef && gets(x, y) == s2) p2 = mp(x, y);
}
}
cout <<p1.first + 1 <<" " <<p1.second + 1 <<endl;
cout <<p2.first + 1 <<" " <<p2.second + 1 <<endl;
} else if(stateDist == 2) {
uint s1 = (1LL * gets(i, j) + 1) % 3;
pair<int, int> p1 = undef;
for(int x = i; x < m; x++) {
for(int y = j; y < n; y++) {
if(p1 != undef && gets(x, y) == s1) p1 = mp(x, y);
}
}
cout <<p1.first + 1 <<" " <<p1.second + 1 <<endl;
}
cout <<m <<" " <<n <<endl;
return 0;
}