This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
#define chmax(a, b) (a = max(1ll * a, 1ll * (b)))
#define chmin(a, b) (a = min(1ll * a, 1ll * (b)))
int qcnt;
bool ask(int x, int y, bool sw) {
if (++qcnt > 300)
exit(0);
if (sw)
swap(x, y);
cout << "examine " << x + 1 << ' ' << y + 1 << endl;
string s;
cin >> s;
return s == "true";
}
ari2 solve(bool sw, int N, int X, int Y) {
if (sw)
swap(X, Y);
int rp = X, hi = N-1;
#ifdef DEBUG
cout << "LOL" << endl;
#endif
while (rp < hi) {
int mid = rp + hi + 1 >> 1;
if (ask(mid, Y, sw))
rp = mid;
else
hi = mid - 1;
}
#ifdef DEBUG
cout << "yeet: " << rp + 1 << endl;
#endif
int S;
if (ask(rp + X >> 1, Y, sw)) {
int lp = 0;
hi = X;
#ifdef DEBUG
cout << "LOL2" << endl;
#endif
while (lp < hi) {
int mid = lp + hi >> 1;
if (ask(mid, Y, sw))
hi = mid;
else
lp = mid + 1;
}
if (ask(lp + rp >> 1, Y, sw)) {
if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
S = rp - lp + 1;
else
S = (rp - lp + 1) / 5;
} else {
S = (rp - lp + 1) / 3;
}
} else {
int lp = X + rp >> 1;
hi = rp;
#ifdef DEBUG
cout << "LOL3" << endl;
#endif
while (lp < hi) {
int mid = lp + hi >> 1;
if (ask(mid, Y, sw))
hi = mid;
else
lp = mid + 1;
}
S = rp - lp + 1;
}
if (rp + 2 * S >= N || !ask(rp + 2 * S, Y, sw))
rp -= 2 * S;
if (rp + 4 * S < N && ask(rp + 4 * S, Y, sw))
return {rp - S + 1, rp + 4 * S};
if (rp >= 2 * S && ask(rp - 2 * S, Y, sw))
return {rp - 3 * S + 1, rp + 2 * S};
return {rp - 2 * S + 1, rp + 3 * S};
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, X, Y;
cin >> N >> X >> Y, X--, Y--;
auto [a, b] = solve(false, N, X, Y);
auto [c, d] = solve(true, N, X, Y);
cout << "solution " << (a + b) / 2 + 1 << ' ' << (c + d) / 2 + 1 << endl;
}
Compilation message (stderr)
aliens.cpp: In function 'ari2 solve(bool, int, int, int)':
aliens.cpp:37:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = rp + hi + 1 >> 1;
| ~~~~~~~~^~~
aliens.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | if (ask(rp + X >> 1, Y, sw)) {
| ~~~^~~
aliens.cpp:54:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int mid = lp + hi >> 1;
| ~~~^~~~
aliens.cpp:60:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | if (ask(lp + rp >> 1, Y, sw)) {
| ~~~^~~~
aliens.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
| ~~~^~~~
aliens.cpp:61:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | if (ask((lp + rp >> 1) + rp >> 1, Y, sw))
| ~~~~~~~~~~~~~~~^~~~
aliens.cpp:69:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int lp = X + rp >> 1;
| ~~^~~~
aliens.cpp:75:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = lp + hi >> 1;
| ~~~^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |