| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 970540 | espnINF | Aliens (IOI07_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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