Submission #651128

#	Time	Username	Problem	Language	Result	Execution time	Memory
651128		ymm	Aliens (IOI07_aliens)	C++17	100 / 100	4 ms	312 KiB

aliens

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#define int ll

int n;

bool query(int i, int j)
{
	if (i < 0 || n <= i || j < 0 || n <= j)
		return 0;
	cout << "examine " << i+1 << ' ' << j+1 << '\n';
	cout.flush();
	string s;
	cin >> s;
	return s[0] == 't';
}

int cnt(int x, int y, int dx, int dy)
{
	int ans = 0;
	for (;;) {
		x += dx;
		y += dy;
		if (!query(x, y))
			break;
		++ans;
	}
	return ans;
}

int bin_cnt_range(int x, int y, int dx, int dy, int l, int r)
{
	while (r - l > 1) {
		int mid = (l+r+1)/2;
		if (query(x + dx*mid, y + dy*mid))
			l = mid;
		else
			r = mid;
	}
	return l;
}

int bin_cnt(int x, int y, int dx, int dy)
{
	int p2;
	for (p2 = 2;; p2 *= 2) {
		if (!query(x + dx*(p2-1), y + dy*(p2-1)))
			break;
	}
	return bin_cnt_range(x, y, dx, dy, p2/2-1, p2-1);
}

signed main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int x0, y0;
	cin >> n >> x0 >> y0;
	--x0; --y0;
	int r = bin_cnt(x0, y0,  1,  0);
	int u = bin_cnt(x0, y0,  0,  1);
	int l = bin_cnt(x0, y0, -1,  0);
	int d = bin_cnt(x0, y0,  0, -1);
	int len = l + r + 1;
	assert(len == u + d + 1);
	assert(len%2 == 1);
	x0 -= l; x0 += len/2;
	y0 -= d; y0 += len/2;
	r = cnt(x0, y0,  2*len,      0);
	u = cnt(x0, y0,      0,  2*len);
	l = cnt(x0, y0, -2*len,      0);
	d = cnt(x0, y0,      0, -2*len);
	if((l + r)%2 == 1) {
		assert((u + d)%2 == 1);
		x0 -= len;
		y0 -= len;
	}
	x0 += 2*len * (1-l);
	y0 += 2*len * (1-d);
	cout << "solution " << x0+1 << ' ' << y0+1 << '\n';
}

• 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