Submission #431184

#	Time	Username	Problem	Language	Result	Execution time	Memory
431184		milleniumEeee	Aliens (IOI07_aliens)	C++17	0 / 100	5 ms	256 KiB

aliens

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define int long long
template<class T>void chmax(T &a, T b){if (a < b)a = b;}
template<class T>void chmin(T &a, T b){if (b < a)a = b;}
using namespace std;

int n, x, y;

bool ask(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= n) {
		cout << "examine " << x << " " << y << endl;
		string res;
		cin >> res;
		return res == "true";		
	} else {
		return false;
	}
}

int last_bit(int x) {
	for (int i = 63; i >= 0; i--) {
		if (x & (1ll << i)) {
			return i;
		}
	}
}

signed main() {
    cin >> n >> x >> y;
    int MIN_Y = -1;
    for (int add = 2; ; add *= 2) {
		if (!ask(x, y - add)) {
			int wy = y - add;
			for (int i = last_bit(add); i >= 0; i--) {
				if (!ask(x, wy + (1ll << i))) {
					wy += (1ll << i);
				}
			}
			MIN_Y = wy + 1;
			break;
		}
	}
    int MIN_X = -1;
	for (int add = 2; ; add *= 2) {
		if (!ask(x - add, y)) {
			int wx = x - add;
			for (int i = last_bit(add); i >= 0; i--) {
				if (!ask(wx + (1ll << i), y)) {
					wx += (1ll << i);
				}
			}
			MIN_X = wx + 1;
			break;
		}
	}
	int MAX_X = -1;
    for (int add = 2; ; add *= 2) {
		if (!ask(x + add, y)) { // white found
			int wx = x + add;
			for (int i = last_bit(add); i >= 0; i--) {
				if (!ask(wx - (1ll << i), y)) {
					wx -= (1ll << i);
				}
			}
			MAX_X = wx - 1;
			break;
		}
	}
	int cur_x = MIN_X;
	int cur_y = MIN_Y;
	int len = MAX_X - MIN_X + 1;
	while (ask(cur_x + len * 2, cur_y + len * 2)) {
		cur_x += len * 2;
		cur_y += len * 2;
	}
	while (ask(cur_x - len * 2, y)) {
		cur_x -= len * 2;
	}
	while (ask(cur_x, y - len * 2)) {
		cur_y -= len * 2;
	}
	cout << cur_x + 2 * len + len / 2 << " " << cur_y + 2 * len + len / 2 << endl;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int last_bit(long long int)':
aliens.cpp:32:1: warning: control reaches end of non-void function [-Wreturn-type]
   32 | }
      | ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10