Submission #530760

#	Time	Username	Problem	Language	Result	Execution time	Memory
530760		pavement	Aliens (IOI07_aliens)	C++17	0 / 100	1 ms	292 KiB

aliens

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, X, Y, M, lo, hi, rans, lans, tans, rcnt, rrig, ttop, posx, posy;

bool qry(int x, int y) {
	if (x < 1 || y < 1 || x > N || y > N) return 0;
	string ret;
	cout << "examine " << x << ' ' << y << endl;
	cin >> ret;
	return ret == "true";
}

main() {
	cin >> N >> X >> Y;
	// go right
	int k;
	for (k = 0; ; k++)
		if (!qry(X + (1 << k), Y)) break;
	// boundary is within (2^(k-1), 2^k]
	lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), rans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (!qry(X + mid, Y)) rans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	cout << rans << '\n';
	for (k = 0; ; k++)
		if (!qry(X - (1 << k), Y)) break;
	// boundary is within (2^(k-1), 2^k]
	lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), lans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (!qry(X - mid, Y)) lans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	
	for (k = 0; ; k++)
		if (!qry(X, Y + (1 << k))) break;
	// boundary is within (2^(k-1), 2^k]
	lo = (k ? (1 << (k - 1)) + 1 : 1), hi = (1 << k), tans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (!qry(X, Y + mid)) tans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	
	rans--, lans--, tans--;
	M = rans + lans + 1;
	X += rans;
	Y += tans;
	
	for (int k = -4; k <= 4; k++) {
		bool tmp = qry(X + k * M, Y);
		rcnt += tmp;
		if (k > 0) rrig += tmp;
	}
	for (int k = 1; k <= 4; k++) {
		bool tmp = qry(X, Y + k * M);
		ttop += tmp;
	}
	if (rcnt == 2) {
		posx = 5 - (1 + 2 * rrig);
		posy = 5 - (1 + 2 * ttop);
	} else {
		assert(rcnt == 3);
		posx = 5 - (2 * rrig);
		posy = 5 - (2 * ttop);
	}
	X += (3 - posx) * M;
	Y += (3 - posy) * M;
	cout << "solution " << X - M / 2 << ' ' << Y - M / 2 << endl;
}

Compilation message (stderr)

aliens.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main() {
      | ^~~~

• 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