Submission #1322316

#TimeUsernameProblemLanguageResultExecution timeMemory
1322316g4yuhgAliens (IOI07_aliens)C++20
0 / 100
0 ms424 KiB
#include<bits/stdc++.h>
//#include "minesweeper.h"
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 500005
#define endl '\n'
#define y0 Y0
using namespace std;

const ll inf = 1e18;

bool ghuy4g;

bool test = 0;

ll n, m, x_ans, y_ans, x0, y0;

ll b[105][105];

bool check(ll x, ll y) {
	if (test) return (b[x][y] > 0);
	bool ok;
	cout << "examine " << x << " " << y << endl; cout.flush();
	cin >> ok;
	return ok;
}

ll min_m = 3;

ll keo(ll x, ll y) {
	if (y > x) return x + 1;
	return x - 1;
}

void solve() {
	if (test) {
		cin >> x0 >> y0;
	}
	else {
		cin >> n >> x0 >> y0;
	}
	ll y_trai = y0, y_phai = y0, x_tren = x0, x_duoi = x0;
	if (1) {
		ll cur_x = x0, cur_y = max(1LL, y0 - min_m), lst = y0;
		while (true) {
			bool flag = check(cur_x, cur_y);
			if (flag == 0 || cur_y == 1) break;
			lst = cur_y;
			min_m = max(min_m, abs(y0 - cur_y) * 2 + 1);
			cur_y = max(1LL, cur_y - min_m);
		}
		ll l = cur_y, r = lst;
		while (l <= r) {
			ll mid = (l + r) / 2;
			bool flag = check(x0, mid);
			if (flag == 1) {
				y_trai = mid;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
	}
	if (1) {
		ll cur_x = x0, cur_y = min(n, y0 + min_m), lst = y0;
		while (true) {
			bool flag = check(cur_x, cur_y);
			if (flag == 0 || cur_y == n) break;
			lst = cur_y;
			min_m = max(min_m, abs(y0 - cur_y) * 2 + 1);
			cur_y = min(n, cur_y + min_m);
		}
		ll l = lst, r = cur_y;
		while (l <= r) {
			ll mid = (l + r) / 2;
			bool flag = check(x0, mid);
			if (flag == 1) {
				l = mid + 1;
				y_phai = mid;
			}
			else {
				r = mid - 1;
			}
		}
	}
	if (1) {
		ll cur_x = max(1LL, x0 - min_m), lst = x0;
		while (true) {
			bool flag = check(cur_x, y0);
			if (test) cout << " cur_x " << cur_x << " " << flag << endl;
			if (flag == 0 || cur_x == 1) break;
			lst = cur_x;
			min_m = max(min_m, abs(x0 - cur_x) * 2 + 1);
			cur_x = max(1LL, cur_x - min_m);
		}
		ll l = cur_x, r = lst;
		while (l <= r) {
			ll mid = (l + r) / 2;
			bool flag = check(mid, y0);
			if (flag == 1) {
				x_tren = mid;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
	}
	if (test) cout << "min m: " << min_m << endl;
	if (1) {
		ll cur_x = min(n, x0 + min_m), lst = x0;
		while (true) {
			bool flag = check(cur_x, y0);
			if (flag == 0 || cur_x == n) break;
			lst = cur_x;
			min_m = max(min_m, abs(x0 - cur_x) * 2 + 1);
			cur_x = min(n, cur_x + min_m);
		}
		ll l = lst, r = cur_x;
		while (l <= r) {
			ll mid = (l + r) / 2;
			bool flag = check(mid, y0);
			if (flag == 1) {
				x_duoi = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
	}
	if (test) {
		cout << "min m: " << min_m << endl;
		cout << "x tren duoi " << x_duoi << " " << x_tren << endl;
		cout << "y tren duoi " << y_trai << " " << y_phai << endl;
	}
	ll tam_x = (x_tren + x_duoi) / 2;
	ll tam_y = (y_trai + y_phai) / 2;
	ll x_ans1 = inf, x_ans2 = 0, y_ans1 = inf, y_ans2 = 0;
	if (1) {
		ll l = 0, r = min(tam_x, tam_y) - 1, ans = -1;
		while (l <= r) {
			ll mid = (l + r) / 2;
			ll xet_x = tam_x - mid, xet_y = tam_y - mid;
			if (xet_x < 1 || xet_y < 1 || xet_x > n || xet_y > n || check(xet_x, xet_y) == 0) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
				ans = mid;
			}
		}
		x_ans1 = min(x_ans1, tam_x - ans);
		x_ans2 = max(x_ans2, tam_x - ans);
		y_ans1 = min(y_ans1, tam_y - ans);
		y_ans2 = max(y_ans2, tam_y - ans);
	}
	if (1) {
		ll l = 0, r = min(n - tam_x, n - tam_y), ans = -1;
		while (l <= r) {
			ll mid = (l + r) / 2;
			ll xet_x = tam_x + mid, xet_y = tam_y + mid;
			if (xet_x < 1 || xet_y < 1 || xet_x > n || xet_y > n || check(xet_x, xet_y) == 0) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
				ans = mid;
			}
		}
		x_ans1 = min(x_ans1, tam_x + ans);
		x_ans2 = max(x_ans2, tam_x + ans);
		y_ans1 = min(y_ans1, tam_y + ans);
		y_ans2 = max(y_ans2, tam_y + ans);
	}
	if (1) {
		ll l = 0, r = min(tam_x - 1, n - tam_y), ans = -1;
		while (l <= r) {
			ll mid = (l + r) / 2;
			ll xet_x = tam_x - mid, xet_y = tam_y + mid;
			if (xet_x < 1 || xet_y < 1 || xet_x > n || xet_y > n || check(xet_x, xet_y) == 0) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
				ans = mid;
			}
		}
		x_ans1 = min(x_ans1, tam_x - ans);
		x_ans2 = max(x_ans2, tam_x - ans);
		y_ans1 = min(y_ans1, tam_y + ans);
		y_ans2 = max(y_ans2, tam_y + ans);
	}
	if (1) {
		ll l = 0, r = min(tam_y - 1, n - tam_x), ans = -1;
		while (l <= r) {
			ll mid = (l + r) / 2;
			ll xet_x = tam_x + mid, xet_y = tam_y - mid;
			if (xet_x < 1 || xet_y < 1 || xet_x > n || xet_y > n || check(xet_x, xet_y) == 0) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
				ans = mid;
			}
		}
		x_ans1 = min(x_ans1, tam_x + ans);
		x_ans2 = max(x_ans2, tam_x + ans);
		y_ans1 = min(y_ans1, tam_y - ans);
		y_ans2 = max(y_ans2, tam_y - ans);
	}
	if (abs(x_ans1 - x_ans2) == abs(y_ans1 - y_ans2)) {
		x_ans = (x_ans1 + x_ans2) / 2;
		y_ans = (y_ans1 + y_ans2) / 2;
		cout << "solution " << x_ans << " " << y_ans << endl;
		cout.flush();
	}
	else if (abs(x_ans1 - x_ans2) > abs(y_ans1 - y_ans2)) {
		x_ans = (x_ans1 + x_ans2) / 2;
		if (tam_y - m / 2 <= y_ans1 && y_ans1 <= tam_y + m / 2) {
			cout << "solution " << x_ans << " " << keo(y_ans2, y_ans1) << endl;
			cout.flush();
		}
		else {
			cout << "solution " << x_ans << " " << keo(y_ans1, y_ans2) << endl;
			cout.flush();
		}
	}
	else {
		y_ans = (y_ans1 + y_ans2) / 2;
		if (tam_x - m / 2 <= x_ans1 && x_ans1 <= tam_x + m / 2) {
			cout << "solution " << keo(x_ans2, x_ans1) << " " << y_ans << endl;
			cout.flush();
		}
		else {
			cout << "solution " << keo(x_ans1, x_ans2) << " " << y_ans << endl;
			cout.flush();
		}
	}
}

void testing() {
	if (test) {
		cin >> n >> m;
		cin >> x_ans >> y_ans;
		cin >> x0 >> y0;
		for (int x = x_ans - m * 2 - m / 2; x <= x_ans - m * 2 - m / 2 + m * 2 * 2; x += m * 2) {
			for (int y = y_ans - m * 2 - m / 2; y <= y_ans - m * 2 - m / 2 + m * 2 * 2; y += m * 2) {
				for (int i = 0; i < m; i ++) {
					for (int j = 0; j < m; j ++) {
						b[x + i][y + j] = 1;
					}
				}
			}
		}
		for (int x = x_ans - m / 2 - m; x <= x_ans - m / 2 - m + m * 2; x += m * 2) {
			for (int y = y_ans - m / 2 - m; y <= y_ans - m / 2 - m + m * 2; y += m * 2) {
				for (int i = 0; i < m; i ++) {
					for (int j = 0; j < m; j ++) {
						b[x + i][y + j] = 1;
					}
				}
			}
		}
		b[x_ans][y_ans] = 2;
		/*for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				cout << b[i][j] << " ";
			}
			cout << endl;
		}*/
	}
	solve();
}

bool klinh;

signed main() {
	if (fopen("kghmdlod.inp", "r")) {
		freopen("kghmdlod.inp", "r", stdin);
		freopen("kghmdlod.out", "w", stdout);
	}
	srand(time(0));
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	testing();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:283:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  283 |                 freopen("kghmdlod.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:284:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  284 |                 freopen("kghmdlod.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...