/*
_____ _ _
/ ____| | | | |
| | __ _ __ __ _ ___ ___ _ _ _ __ ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
\_____|_| \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
__/ | |
|___/|_|
*/
#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
//#define f first
//#define s second
#define sz size
#define pob pop_back
#define pf push_front
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define asg assign
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))
#define HEX 0x3f3f3f3f
using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};
int query(int x, int y) {
cout << "examine" << ' ' << x << ' ' << y << endl;
string s;
cin >> s;
return s == "true";
}
int main()
{
std::ios_base::sync_with_stdio(false); cin.tie(0);
int n, x0, y0;
cin >> n >> x0 >> y0;
// find right coordinate of initial square
int l = x0, r = x0;
FOR(i, 0, 32) {
if (!query(x0 + (1 << i), y0)) {
r = x0 + (1 << i);
break;
}
}
int right = -1;
while (l <= r) {
int m = (l + r + 1) / 2;
if (query(m, y0)) {
right = m;
l = m + 1;
} else {
r = m - 1;
}
}
// find left coordinate of initial square
l = x0, r = x0;
FOR(i, 0, 31) {
if (!query(x0 - (1 << i), y0)) {
l = x0 - (1 << i);
break;
}
}
int left = -1;
while (l <= r) {
int m = (l + r) / 2;
if (query(m, y0)) {
left = m;
r = m - 1;
} else {
l = m + 1;
}
}
// find top coordinate of initial square
int t = y0, b = y0;
FOR(i, 0, 31) {
if (!query(x0, y0 + (1 << i))) {
t = y0 + (1 << i);
break;
}
}
int top = -1;
while (b <= t) {
int m = (t + b) / 2;
if (query(x0, m)) {
top = m;
b = m + 1;
} else {
t = m - 1;
}
}
int m = right - left + 1;
// cerr << m << ' ' << left << ' ' << right << ' ' << top << endl;
int cx = left + (m - 1) / 2, cy = top - (m - 1) / 2;
// cerr << cx << ' ' << cy << endl;
int lx = cx;
FOR(i, 1, 3) {
if (query(lx - 2 * m * i, cy)) {
lx -= 2 * m;
} else {
break;
}
}
int rx = cx;
FOR(i, 1, 3) {
if (query(cx + 2 * m * i, cy)) {
rx += 2 * m;
} else {
break;
}
}
int tx = cy;
FOR(i, 1, 3) {
if (query(cx, cy + 2 * m * i)) {
tx += 2 * m;
} else {
break;
}
}
int bx = cy;
FOR(i, 1, 3) {
if (query(cx, cy - 2 * m * i)) {
bx -= 2 * m;
} else {
break;
}
}
// cerr << lx << ' ' << rx << ' ' << tx << ' ' << bx << endl;
cout << "solution " << (lx + rx) / 2 << ' ' << (tx + bx) / 2 << '\n';
return 0;
}
/*
* Find M by finding the top, left, and right coordinates
* of the initial square
*
* Since the checkeboards are spaced 2 * M apart,
* test 2^0, 2^1, 2^x until you find a white cell
* Then binary search for the black square
*
* Find the center of that square
* Shift left, right, up, and down until you
* find an empty square to find its bounds
*
* Then find the center of those four points
*/
//
Compilation message
aliens.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
12 | #pragma gcc target ("avx2")
|
aliens.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
13 | #pragma gcc optimization ("O3")
|
aliens.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
14 | #pragma gcc optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
208 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
208 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
208 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
2 ms |
208 KB |
Incorrect |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
208 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
312 KB |
Execution killed with signal 13 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
312 KB |
Execution killed with signal 13 |
| 3 |
Halted |
0 ms |
0 KB |
- |
