Submission #1275036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275036		rana_azka	Mađioničar (COI22_madionicar)	C++20	13 / 100	484 ms	1428 KiB

Main

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

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 2e5;

int n, m;
int arr[MAXN+5];

bool query(int l, int r){
    cout << "? " << l << ' ' << r << endl;
    int jury; cin >> jury;
    return jury;
}

bool cek(int target){
    for(int i = 1; i <= n - target + 1; i++){
        if(query(i, i + target - 1)) return 1;
    }

    return 0;
}

void solve(){
    cin >> n;

    vector<int> odd, even;
    for(int i = 1; i <= n; i++){
        if(i % 2) odd.push_back(i);
        else even.push_back(i);
    }

    int ans = 0;
    int left = 0, right = (int)odd.size() - 1;
    int mid;
    while(left <= right){
        mid = (left + right) / 2;

        if(cek(odd[mid])){
            ans = max(odd[mid], ans);
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    left = 0, right = (int)even.size() - 1;
    mid = 0;
    while(left <= right){
        mid = (left + right) / 2;

        if(even[mid] < ans || cek(even[mid])){
            ans = max(even[mid], ans);
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    cout << "! " << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        solve();
    }

    return 0;
}

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