# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
280226 | spdskatr | Colors (BOI20_colors) | C++14 | 1 ms | 416 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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cassert>
#include <vector>
#define K 32
using namespace std;
int N;
int seen[1005];
vector<int> qu;
int last = 6969, actual;
int query(int x) {
#ifdef DEBUG
//printf("query(%d)\n", x);
assert(x > 0 && x <= N);
int r = abs(x - last) >= actual;
last = x;
return r;
#else
printf("? %d\n", x);
fflush(stdout);
int res;
scanf("%d", &res);
last = x;
return res;
#endif
}
void answer(int ans) {
printf("= %d\n", ans);
fflush(stdout);
exit(0);
}
int main() {
scanf("%d", &N);
#ifdef DEBUG
scanf("%d", &actual);
#endif
assert(N <= 1000);
qu.push_back(0);
for (int i = 1; i * K < N; i++) {
if (qu.size() <= 1 || qu[qu.size()-1] < qu[qu.size()-2]) {
qu.push_back(qu.back() + i * K);
} else {
qu.push_back(qu.back() - i * K);
}
}
// Stick to left
int diff = 1 - qu.back();
if (qu.back() > 0) {
// Last move was forward, stick to right
diff = N - qu.back();
}
for (int i = 0; i < qu.size(); i++) qu[i] += diff;
for (int i = 0; i < qu.size(); i++) {
int res = query(qu[i]);
if (i > 0 && res) {
int low = 0;
int cur = qu[i];
int par = cur > qu[0];
if (i >= 2) low = abs(qu[i-1] - qu[i-2]);
for (int j = abs(qu[i] - qu[i-1]) - 1; j > low; j--) {
if (par) {
cur -= j;
} else {
cur += j;
}
par = !par;
if (!query(cur)) {
answer(j+1);
}
}
answer(low+1);
}
}
// Should either be at N or 1
{
int cur = qu.back();
int par = cur <= qu[0];
for (int j = N-1; j > ((N-1) / K) * K; j--) {
if (par) {
cur += j;
} else {
cur -= j;
}
par = !par;
if (!query(cur)) {
answer(j+1);
}
}
answer(((N-1) / K) * K + 1);
}
}
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... |