Submission #260721

#TimeUsernameProblemLanguageResultExecution timeMemory
260721BruteforcemanColors (BOI20_colors)C++11
67 / 100
2 ms500 KiB
#include <bits/stdc++.h>
using namespace std;
long long last, C;
set <long long> cont;
long long N;

int ask(long long x) {
  cout << "? " << x << endl;
  assert(cont.count(x) == 0);
  assert(1 <= x && x <= N);
  cont.insert(x);
  int ans = (abs(x - last) >= C);
  cin >> ans;
  last = x;
  return ans;
}
long long solve(long long start, long long diff, long long step) {
  if(step == 1) {
    ask(start);
    return abs(diff);
  }
  long long ans;
  if(step % 2 == 0) {
    long long last = start + (step - 1) * diff;
    long long var = solve(last, -diff * 2, step / 2);
    long long check = diff > 0 ? last - var + diff : last + var + diff;
    if(ask(check)) ans = var - abs(diff);
    else ans = var;
    if(check != start) ask(start);
  } else {
    long long last = start + diff;
    long long var = solve(last, diff * 2, step / 2);
    long long check = diff > 0 ? last + var - diff : last - var - diff;

    if(ask(check)) {
      ans = var - abs(diff);
      ask(start);
    } else if (ask(start)) {
      ans = var;
    } else {
      ans = var + abs(diff);
    }
  }
  return ans;
}
int main() {
  C = 556;
  cin >> N;
  long long ans = solve(1, 1, N);
  cout << "= " << ans << endl;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...