【題解】Codeforces 1486C2. Guessing the Greatest (hard version)

【題目敘述】http://codeforces.com/problemset/problem/1486/C2

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

int query(int l, int r){
    assert(l < r);
    int ret;
    cout << "? " << l << " " << r << "\n";
    cin >> ret;
    return ret;
}

int main(){
    int n;
    cin >> n;
    int sec = query(1, n);
    if (sec == n || query(sec, n) != sec){
        int l = 1, r = sec;
        while (r-l > 1){
            int mid = (l+r)/2;
            if (query(mid, sec) == sec) l = mid;
            else r = mid;
        }
        cout << "! " << l << "\n";
    }
    else{
        int l = sec, r = n;
        while (r-l > 1){
            int mid = (l+r)/2;
            if (query(sec, mid) == sec) r = mid;
            else l = mid;
        }
        cout << "! " << r << "\n";
    }
}
分享本文 Share with friends