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>
#define nl '\n'
long long N;
std::array<long long, 2> P0;
long long ask(std::array<long long, 2> P) {
auto [x, y] = P;
assert(1 <= x && x <= N && 1 <= y && y <= N);
std::cout << "examine " << x << " " << y << std::endl;
std::string res;
std::cin >> res;
return res == "true";
}
void answer(long long x, long long y) {
assert(1 <= x && x <= N && 1 <= y && y <= N);
std::cout << "solution " << x << " " << y << std::endl;
}
std::array<long long, 2> bin_search(std::array<long long, 2> P, int c) {
long long ans = P[c];
long long lb = P[c] + 1, rb = N;
while (lb <= rb) {
auto m = (lb + rb) / 2;
auto A = P;
A[c] = m;
if (ask(A)) {
ans = m;
lb = m + 1;
} else {
rb = m - 1; // this is not it
}
}
P[c] = ans;
return P;
}
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N >> P0[0] >> P0[1];
auto R = bin_search(P0, 0); // find biggest x
auto U = bin_search(R, 1); // find biggest y
int rb = std::min(N - U[0], N - U[1]);
int lb = 1;
int ans = 0;
while (lb <= rb) {
int m = (lb + rb) / 2;
if (ask({U[0] + m, U[1] + m})) {
ans = m;
lb = m + 1;
} else {
rb = m - 1;
}
}
auto UR = U;
UR[0] += ans;
UR[1] += ans;
lb = 1;
rb = std::min(U[0] - 1, U[1] - 1);
ans = 0;
while (lb <= rb) {
int m = (lb + rb) / 2;
if (ask({U[0] - m, U[1] - m})) {
ans = m;
lb = m + 1;
} else {
rb = m - 1;
}
}
auto LL = U;
LL[0] -= ans;
LL[1] -= ans;
U = {(LL[0] + UR[0]) / 2, (LL[1] + UR[1]) / 2};
rb = std::min(U[0] - 1, N - U[1]); // -, +
lb = 1;
ans = 0;
while (lb <= rb) {
int m = (lb + rb) / 2;
if (ask({U[0] - m, U[1] + m})) {
ans = m;
lb = m + 1;
} else {
rb = m - 1;
}
}
UR = U;
UR[0] -= ans;
UR[1] += ans;
lb = 1;
rb = std::min(N - U[0], U[1] - 1);
ans = 0;
while (lb <= rb) {
int m = (lb + rb) / 2;
if (ask({U[0] + m, U[1] - m})) {
ans = m;
lb = m + 1;
} else {
rb = m - 1;
}
}
LL = U;
LL[0] -= ans;
LL[1] -= ans;
U = {(LL[0] + UR[0]) / 2, (LL[1] + UR[1]) / 2};
answer(U[0], U[1]);
}
/*
45 9
19 9
23 23
1 9 0
10 18 1
19 27 2
28 36 3
37 45 4
3 0
*/
# | 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... |