제출 #1275130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275130		rana_azka	Mađioničar (COI22_madionicar)	C++20	13 / 100	512 ms	1324 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;

bool query(int l, int r){
    cout << "? " << l << ' ' << r << endl;
    bool 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 cnt = 0;

    int ans = 0;
    int left = 0, right = odd.size();
    right--;
    int mid;
    while(left <= right){
        mid = (left + right) / 2;
        
        if(cek(odd[mid])){
            ans = max(odd[mid], ans);
            if(n > 7500 && cnt >= 4){
                cout << "! " << odd[mid] << endl;
                return ;
            }
            left = mid + 1;
        }else{
            right = mid - 1;
        }
        cnt++;
    }
    
    left = 0; right = even.size();
    right--;
    mid = 0;
    while(left <= right){
        mid = (left + right) / 2;
        
        if(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