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;
#define int long long
int a_;
int ask(int c) {
printf("? %lld\n", c);
fflush(stdout);
scanf("%lld", &a_);
return a_;
}
void report(int C) {
printf("= %lld\n", C);
fflush(stdout);
exit(0);
}
signed main() {
int n = 1e18;
cin >> n;
if (n <= 64) {
if (n == 1) report(1);
ask(1);
if (!ask(n)) report(n);
for (int r = n - 1, l = 2, d = n - 1, i = 1, cc = 0; cc < n - 2;
++i, --d, ++cc)
if (i % 2 && !ask(l++))
report(d);
else if (i % 2 == 0 && !ask(r--))
report(d);
report(1);
return 0;
}
vector<int> precomp;
int l = 1, r = n;
while (l < r) {
precomp.push_back((l + r) / 2);
l = (l + r) / 2 + 1;
}
int cur = n;
int left = 1;
reverse(precomp.begin(), precomp.end());
for (auto a : precomp) {
if (left == 0) {
cur += a;
left = 1;
} else if (left == 1) {
cur -= a;
left = 0;
}
}
int tmpcur = cur, tmpleft = left;
// for (int ans = 1e18; ans >= 1e18 - 1e6; ans--) {
// if (ans % 100 == 0) cout << ans << " ";
int res;
cout << "? " << cur << endl;
cin >> res;
cur = tmpcur, left = tmpleft;
set<int> si;
si.insert(cur);
l = 1, r = n;
while (l < r) {
int mid = (l + r) / 2;
int guess;
if (left) {
guess = cur - mid;
left = 0;
} else {
guess = cur + mid;
left = 1;
}
if (si.count(guess)) {
while (1) {
}
// cout << "FAILED " << ans << '\n';
return 0;
}
si.insert(guess);
cur = guess;
// if (mid >= ans)
// r = mid;
// else
// l = mid + 1;
cout << "? " << cur << endl;
cin >> res;
if (res)
r = mid;
else
l = mid + 1;
}
cout << "= " << l << endl;
// if (l != ans) {
// cout << "WRONG " << ans << ' ' << l << '\n';
// return 0;
// }
// }
}
Compilation message (stderr)
Colors.cpp: In function 'long long int ask(long long int)':
Colors.cpp:8:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | scanf("%lld", &a_);
| ~~~~~^~~~~~~~~~~~~
# | 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... |