Submission #119275

#	Time	Username	Problem	Language	Result	Execution time	Memory
119275		eriksuenderhauf	Aliens (IOI07_aliens)	C++11	100 / 100	4 ms	412 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char resp[30];
ll n, x, y;

bool qry(ll x0, ll y0) {
	if (x0 > n || y0 > n || x0 < 1 || y0 < 1)
		return false;
	printf("examine %lld %lld\n", x0, y0);
	fflush(stdout);
	scanf("%s", resp);
	return resp[0] == 't';
}

ll solveX(ll dir) {
	for (ll i = 1;; i *= 2) {
		if (qry(x + i * dir, y)) continue;
		if (i == 1) return x;
		ll lo = x + dir * i / 2, hi = x + dir * i;
		while (abs(hi - lo) > 1) {
			ll mi = (lo + hi) / 2;
			if (qry(mi, y))
				lo = mi;
			else
				hi = mi;
		}
		return lo;
	}
	return dir > 0 ? n : 1;
}

ll solveY(ll dir) {
	for (ll i = 1;; i *= 2) {
		if (qry(x, y + i * dir)) continue;
		if (i == 1) return y;
		ll lo = y + dir * i / 2, hi = y + dir * i;
		while (abs(hi - lo) > 1) {
			ll mi = (lo + hi) / 2;
			if (qry(x, mi))
				lo = mi;
			else
				hi = mi;
		}
		return lo;
	}
	return dir > 0 ? n : 1;
}

ll cnt[4];
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

int main() {
	scanf("%lld %lld %lld", &n, &x, &y);
	ll mxx = solveX(1), mix = solveX(-1);
	ll mxy = solveY(1), miy = solveY(-1);
	x = (mxx+mix) / 2;
	y = (mxy+miy) / 2;
	ll m = mxx - mix + 1;
	for (ll i = 0; i < 4; i++) {
		for (cnt[i] = 1; qry(x + 2 * m * dx[i] * cnt[i], y + 2 * m * dy[i] * cnt[i]); cnt[i]++);
		cnt[i]--;
	}
	if (cnt[0] == cnt[2] && cnt[1] == cnt[3])
		return !printf("solution %lld %lld\n", x, y);
	x = x + m * (cnt[0] * dx[0] + cnt[2] * dx[2]);
	y = y + m * (cnt[1] * dy[1] + cnt[3] * dy[3]);
	printf("solution %lld %lld\n", x, y);
    return 0;
}

Compilation message (stderr)

aliens.cpp: In function 'bool qry(ll, ll)':
aliens.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", resp);
  ~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld", &n, &x, &y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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