Submission #757821

#	Time	Username	Problem	Language	Result	Execution time	Memory
757821		taher	Mađioničar (COI22_madionicar)	C++17	100 / 100	1952 ms	444 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  auto Ask = [&](int l, int r) {
    ++l, ++r;
    cout << "? " << l << " " << r << endl;
    int ret;
    cin >> ret;
    return ret;
  };
  int cur = 1;
  int res = 1;

  auto SolveOdd = [&](int it) {
    int lowOdd = it - cur;
    int highOdd = it + cur;
    bool foundOdd = false;
    while (lowOdd >= 0 && highOdd < n && Ask(lowOdd, highOdd) == 1) {
      foundOdd = true;
      lowOdd -= 1;
      highOdd += 1;
      cur += 1;
    }
    if (foundOdd) {
      cur -= 1;
      res = max(res, cur * 2 + 1);
      cur += 1;
    }
    return ;
  };

  auto SolveEven = [&](int it) {
    bool foundEven = false;
    int lowEven = it - cur + 1;
    int highEven = it + cur;
    while (lowEven >= 0 && highEven < n && Ask(lowEven, highEven) == 1) {
      foundEven = true;
      lowEven -= 1;
      highEven += 1;
      cur += 1;
    }
    if (foundEven) {
      cur -= 1;
      res = max(res, cur * 2);
      cur += 1;
    }    
  };

  for (int i = 0; i < n; i++) {
    SolveOdd(i);
  }
  for (int i = 0; i < n; i++) {
    SolveEven(i);
  }
  cout << "! " << res << endl;
  return 0; 
}

• Subtask 1: 13 / 13
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37