Submission #642272

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

Colors

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

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

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;
  };
  set<int> asked;
  int m = (1 + n) / 2;
  int l1 = 1, r1 = m;
  int l2 = m, r2 = n;
  ask((l1 + r1) / 2);
  asked.insert((l1 + r1) / 2);
  bool g = false;
  int ans = 1;
  while (l1 < r1 && l2 < r2) {
    int m1 = (l1 + r1) / 2;
    int m2 = (l2 + r2) / 2;
    int ret;
    if (g == false) {
      if (asked.find(m2) != asked.end()) break;
      ret = ask(m2);
      asked.insert(m2);
    } else {
      if (asked.find(m1) != asked.end()) break;
      ret = ask(m1);
      asked.insert(m1);
    }
    if (g == false) { // m1
      if (ret) {
        ans = max(ans, abs(m2 - m1));
        r1 = m1;
      } else {
        l1 = m1;
      }
    } else { // m2
      if (ret) {
        ans = max(ans, abs(m2 - m1));
        l2 = m2;
      } else {
        r2 = m2;
      }
    }
    g ^= true;
  }
  cout << "= " << ans << endl;
}

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