Submission #747085

#	Time	Username	Problem	Language	Result	Execution time	Memory
747085		MilosMilutinovic	Mađioničar (COI22_madionicar)	C++14	100 / 100	1847 ms	208 KiB

Main

/**
 *    author:  wxhtzdy
 *    created: 05.07.2022 14:44:38
**/
#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) {
    cout << "? " << l + 1 << " " << r + 1 << endl;
    int x;
    cin >> x;
    return x; 
  };
  int ans = 1;
  for (int i = 1; i < n; i++) {
    while (true) {
      int l = i - (ans + 1) / 2;
      int r = i + (ans + 1) / 2;
      if (l < 0 || r >= n || !Ask(l, r)) {
        break;
      }
      ans = r - l + 1;
    }
  }
  for (int i = 0; i + 1 < n; i++) {
    while (true) {
      int l = i - (ans % 2 == 1 ? (ans - 1) / 2 : ans / 2);
      int r = i + 1 + (ans % 2 == 1 ? (ans - 1) / 2 : ans / 2);
      if (l < 0 || r >= n || !Ask(l, r)) {
        break;
      }
      ans = r - l + 1;
    }
  }
  cout << "! " << ans << endl;                  
  return 0;
}

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