Submission #642329

#	Time	Username	Problem	Language	Result	Execution time	Memory
642329		MKutayBozkurt	Colors (BOI20_colors)	C++17	0 / 100	1 ms	464 KiB

Colors

#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
  #include "/Users/kutay/CP/templates/debug.h"
#else
  #define debug(...) void(38)
#endif

#define int long long

int32_t main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  auto ask = [&](int p) {
    cout << "? " << p << endl;
    int x; cin >> x;
    return x;
  };
  function<int(int, int, int)> f = [&](int l, int r, int last) {
    debug(l, r, last);
    if (l == r) return l;
    int mm = r - l + 1;
    int lg = log2(mm);
    if ((1 << lg) != mm) mm = (1 << (lg + 1));
    int m = l + mm / 2 - 1;
    int next = -1;
    if (last + m <= n) {
      next = last + m;
    } else if (last - m > 0) {
      next = last - m;
    } else assert(false);
    int ret = ask(next);
    if (ret == 1) {
      return f(l, m, next);
    } else {
      return f(m + 1, r, next);
    }
  };
  int m = (1 + n) / 2 + (n & 1 ? 1 : 2);
  ask(m);
  int ans = f(1, n, m);
  cout << "= " << ans << endl;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 33