#include <bits/stdc++.h>
using namespace std;
#define ll long long
// template thingy
#ifdef __cplusplus
extern "C" {
#endif
int examine(int X, int Y);
void solution(int XC, int YC);
void findCenter(ll N, ll X0, ll Y0);
#ifdef __cplusplus
}
#endif
bool deb = 0; // toggle debug mode, **CHANGE**
ll m, n, x, y, a, b, c, d, l, r, mid, p, q, up, down, le, ri, length;
ll binsearch1(ll l, ll r, bool f) { // right or up, f = 1 --> y
while (l <= r) {
if (l == r) break;
else if (l == r - 1) {
if (deb) cout << (f == 0 ? r : x) << ' ' << (f == 0 ? y : r) << '\n';
if (examine((f == 0 ? r : x), (f == 0 ? y : r))) l = r;
else r = l;
break;
}else {
mid = (l + r) / 2;
if (!examine((f == 0 ? mid : x), (f == 0 ? y : mid))) r = mid;
else l = mid;
}
}
return l;
}
ll binsearch2(ll l, ll r, bool f) { // left or down
while (l <= r) {
if (l == r) break;
else if (l == r - 1) {
if (deb) cout << (f == 0 ? l : x) << ' ' << (f == 0 ? y : l) << '\n';
if (examine((f == 0 ? l : x), (f == 0 ? y : l))) r = l;
else l = r;
break;
}else {
mid = (l + r) / 2;
if (!examine((f == 0 ? mid : x), (f == 0 ? y : mid))) l = mid;
else r = mid;
}
}
return l;
}
#define so solution
void findCenter(ll N, ll X0, ll Y0) {
up = 0, down = 0, le = 0, ri = 0;
x = X0; y = Y0; n = N;
bool t = 1;
if (deb) cout << "#1\n";
for (int i = 1; x <= n; i *= 2) {
x += i;
if (x - i == n) break;
if (x > n) x=n;
if (!examine(x, y)) {
c = binsearch1(x - i, x, 0);
t = 0;
break;
}
}
if (t) c = n;
t = 1;
x = X0;
if (deb) cout << "#2\n";
for (int i = 1; y <= n; i *= 2) {
y += i;
if (y - i == n) break;
if (y > n) y=n;
if (!examine(x, y)) {
d = binsearch1(y - i, y, 1);
t = 0;
break;
}
}
if (t) d = n;
t = 1;
y = Y0;
if (deb) cout << "#3\n";
for (int i = 1; x >= 1; i *= 2) {
x -= i;
if (x + i == 1) break;
if (x < 1) x=1;
if (!examine(x, y)) {
if (deb) cout << x << ' ' << x + i << '\n';
a = binsearch2(x, x + i, 0);
t = 0;
break;
}
}
if (t) a = 1;
t = 1;
x = X0;
b = d - (c - a);
length = c - a + 1;
if (deb) {
cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
cout << length << "\n";
}
// for (int i = 1; y >= 1; i *= 2) {
// y -= i;
// if (!examine(x, y)) {
// b = binsearch2(y, y + i, 1);
// t = 0;
// break;
// }
// }
// if (t) b = 1;
// t = 1;
// y = Y0;
p = (a + c) / 2;
q = (b + d) / 2;
if (deb) cout << p << ' ' << q << "\n";
// left
if (x - 2 * length >= 1) le += examine(x - 2 * length, y);
if (x - 4 * length >= 1) le += examine(x - 4 * length, y);
// right (not necessary)
if (x + 2 * length <= n and deb) ri += examine(x + 2 * length, y);
if (x + 4 * length <= n and deb) ri += examine(x + 4 * length, y);
// up
if (y + 2 * length <= n) up += examine(x, y + 2 * length);
if (y + 4 * length <= n) up += examine(x, y + 4 * length);
// down
if (y - 2 * length >= 1) down += examine(x, y - 2 * length);
if (y - 4 * length >= 1) down += examine(x, y - 4 * length);
if (deb) cout << up << ' ' << down << ' ' << le << ' ' << ri << "\n";
// 13 cases
if (up == 0) {
if (down == 2) {
if (le == 0) so(p + 2 * length, q - 2 * length);
else if (le == 1) so(p, q - 2 * length);
else so(p - 2 * length, q - 2 * length);
}else {
if (le == 0) so(p + length, q - length);
else so(p - length, q - length);
}
}else if (up == 1) {
if (down == 1) {
if (le == 0) so(p + 2 * length, q);
else if (le == 1) so(p, q);
else so(p - 2 * length, q);
}else {
if (le == 0) so(p + length, q + length);
else so(p - length, q + length);
}
}else {
if (le == 0) so(p + 2 * length, q + 2 * length);
else if (le == 1) so(p, q + 2 * length);
else so(p - 2 * length, q + 2 * length);
}
return;
}
// binsearch so annoying
Compilation message
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
/usr/bin/ld: /tmp/cc4dGDKJ.o: in function `binsearch1(long long, long long, bool)':
aliens.cpp:(.text+0x49): undefined reference to `examine'
/usr/bin/ld: aliens.cpp:(.text+0x8b): undefined reference to `examine'
/usr/bin/ld: aliens.cpp:(.text+0x132): undefined reference to `examine'
/usr/bin/ld: /tmp/cc4dGDKJ.o: in function `binsearch2(long long, long long, bool)':
aliens.cpp:(.text+0x1d9): undefined reference to `examine'
/usr/bin/ld: aliens.cpp:(.text+0x21b): undefined reference to `examine'
/usr/bin/ld: /tmp/cc4dGDKJ.o:aliens.cpp:(.text+0x2c2): more undefined references to `examine' follow
/usr/bin/ld: /tmp/cc4dGDKJ.o: in function `findCenter':
aliens.cpp:(.text+0x722): undefined reference to `solution'
/usr/bin/ld: aliens.cpp:(.text+0x839): undefined reference to `solution'
collect2: error: ld returned 1 exit status
