oj.uz

Submission #651128

# Submission time Handle Problem Language Result Execution time Memory
651128 2022-10-17T10:01:12 Z ymm Aliens (IOI07_aliens) C++17
100 / 100
 4 ms 312 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 4 ms 208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 2 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct