Submission #1347533

#TimeUsernameProblemLanguageResultExecution timeMemory
1347533viduxAliens (IOI07_aliens)C++17
100 / 100
1 ms436 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
        ios::sync_with_stdio(0), cin.tie(0);
	ll n, x, y; cin >> n >> x >> y;
	auto query = [&](ll x, ll y) -> bool {
		if (x < 1 || y < 1 || x > n || y > n) return 0;
		cout << "examine " << x << " " << y << endl;
		cout.flush();
		string resp; cin >> resp;
		return resp == "true";
	};
	auto search = [&](ll dx, ll dy) -> ll {
		ll cx = x, cy = y;
		int i;
		for (i = 0; i < 32; i++) {
			ll nx = cx+dx*(1ll<<i);
			ll ny = cy+dy*(1ll<<i);
			bool f = query(nx, ny);
			if (!f) break;
			cx = nx;
			cy = ny;
		}
		i--;
		for (; i >= 0; i--) {
			ll nx = cx+dx*(1ll<<i);
			ll ny = cy+dy*(1ll<<i);
			bool f = query(nx, ny);
			if (f) {
				cx = nx;
				cy = ny;
			}
		}
		return abs(cx-x)+abs(cy-y);
	};
	ll wr = search(1, 0);
	ll wl = search(-1, 0);
	ll hu = search(0, 1);
	ll hd = search(0, -1);
	ll m = wr+wl+1;
	x += (wr-wl)/2;
	y += (hu-hd)/2;
	ll rx = x, uy = y, lx = x, dy = y;
	for (int i = 0; i < 3; i++, rx += 2*m) if (!query(rx+2*m, y)) break;
	for (int i = 0; i < 3; i++, uy += 2*m) if (!query(x, uy+2*m)) break;
	for (int i = 0; i < 3; i++, lx -= 2*m) if (!query(lx-2*m, y)) break;
	for (int i = 0; i < 3; i++, dy -= 2*m) if (!query(x, dy-2*m)) break;
	x = (rx+lx)/2, y = (uy+dy)/2;
	cout << "solution " << x << " " << y << endl;
}
#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...