제출 #1325237

#제출 시각아이디문제언어결과실행 시간메모리
1325237ppmn_6Aliens (IOI07_aliens)C++20
100 / 100
1 ms332 KiB
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	ll x, y;
	cin >> n >> x >> y;
	auto query = [&] (int a, int b) {
		cout << "examine " << a << " " << b << endl;
		string res;
		cin >> res;
		return res == "true";
	};
	ll lx = 0, rx = 0, ly = 0, ry = 0;
	if (x == 1 || !query(x - 1, y)) {
		lx = x;
	}
	else {
		ll l = 1, r = x - 1;
		while (query(x - l, y)) {
			if (x - l == 1) {
				lx = 1;
				break;
			}
			l = min(l * 2, r);
		}
		if (!lx) {
			r = l - 1;
			l /= 2;
			while (r - l > 2) {
				ll m = (l + r) / 2;
				if (query(x - m, y)) {
					l = m;
				}
				else {
					r = m;
				}
			}
			if (query(x - r, y)) {
				lx = x - r;
			}
			else if (query(x - r + 1, y)) {
				lx = x - r + 1;
			}
			else {
				lx = x - l;
			}
		}
	}
	if (x == n || !query(x + 1, y)) {
		rx = x;
	}
	else {
		ll l = 1, r = n - x;
		while (query(x + l, y)) {
			if (x + l == n) {
				rx = n;
				break;
			}
			l = min(l * 2, r);
		}
		if (!rx) {
			r = l - 1;
			l /= 2;
			while (r - l > 2) {
				ll m = (l + r) / 2;
				if (query(x + m, y)) {
					l = m;
				}
				else {
					r = m;
				}
			}
			if (query(x + r, y)) {
				rx = x + r;
			}
			else if (query(x + r - 1, y)) {
				rx = x + r - 1;
			}
			else {
				rx = x + l;
			}
		}
	}
	if (y == 1 || !query(x, y - 1)) {
		ly = y;
	}
	else {
		ll l = 1, r = y - 1;
		while (query(x, y - l)) {
			if (y - l == 1) {
				ly = 1;
				break;
			}
			l = min(l * 2, r);
		}
		if (!ly) {
			r = l - 1;
			l /= 2;
			while (r - l > 2) {
				ll m = (l + r) / 2;
				if (query(x, y - m)) {
					l = m;
				}
				else {
					r = m;
				}
			}
			if (query(x, y - r)) {
				ly = y - r;
			}
			else if (query(x, y - r + 1)) {
				ly = y - r + 1;
			}
			else {
				ly = y - l;
			}
		}
	}
	ll m = rx - lx + 1;
	ry = ly + m - 1;
	ll cx = lx + m / 2, cy = ly + m / 2;
	int cntl = 0, cntr = 0, cntu = 0, cntd = 0;
	if (cx - 2 * m >= 1 && query(cx - 2 * m, cy)) {
		cntl++;
	}
	if (cx - 4 * m >= 1 && query(cx - 4 * m, cy)) {
		cntl++;
	}
	if (cx + 2 * m <= n && query(cx + 2 * m, cy)) {
		cntr++;
	}
	if (cx + 4 * m <= n && query(cx + 4 * m, cy)) {
		cntr++;
	}
	if (cy - 2 * m >= 1 && query(cx, cy - 2 * m)) {
		cntu++;
	}
	if (cy - 4 * m >= 1 && query(cx, cy - 4 * m)) {
		cntu++;
	}
	if (cy + 2 * m <= n && query(cx, cy + 2 * m)) {
		cntd++;
	}
	if (cy + 4 * m <= n && query(cx, cy + 4 * m)) {
		cntd++;
	}
	cx -= cntl * m;
	cx += cntr * m;
	cy -= cntu * m;
	cy += cntd * m;
	cout << "solution " << cx << " " << cy << endl;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...