# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
810216 | ymm | Colors (BOI20_colors) | C++17 | 3066 ms | 208 KiB |
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>
typedef long long ll;
using namespace std;
set<ll> S;
bool query(ll x)
{
assert(!S.count(x));
S.insert(x);
int d;
printf("? %lld\n", x+1);
fflush(stdout);
scanf("%d", &d);
return d;
}
int main()
{
ll n;
scanf("%lld", &n);
ll pos = n/2+1;
query(pos);
ll l = 1, r = n;
while (l < r) {
ll m0 = (l+r)/2;
ll x = pos < n/2? 1: -1;
//cerr << l << ' ' << r << ' ' << pos+1 << ' ' << m0 << '\n';
ll m;
for (ll i = 0;; ++i) {
ll dard = i%2? i/2+1: -i/2;
//ll dard = i%2? -i/2+1: i/2;
ll pos2 = pos + x*(m0+dard);
if (pos2 < 0 || n <= pos2 || S.count(pos2))
continue;
m = m0+dard;
break;
}
if (query(pos = pos + x*m))
r = m;
else
l = m+1;
}
printf("= %lld\n", l);
}
Compilation message (stderr)
# | 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... |