Codeforces Round #703 (Div. 2)C (二分)

 1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
 2 #define bug(x) cout<<#x<<" is "<<x<<endl
 3 #include <bits/stdc++.h>
 4 #define iter ::iterator
 5 using namespace  std;
 6 typedef long long ll;
 7 typedef pair<int,ll>P;
 8 #define pb push_back
 9 #define mk make_pair
10 #define se second
11 #define fi first
12 #define rs o*2+1
13 #define ls o*2
14 const ll inf=1e18;
15 const int N=1e3+5;
16 
17 int T,n,res;
18 
19 int qu(int x,int y){
20     cout<<"? "<<x<<" "<<y<<endl;
21     int z;
22     cin>>z;
23     return z;
24 }
25 
26 int gao1(int L,int R){
27     int l=L,r=R,m=L;
28     while(l<r-1){
29         m=(l+r)/2;
30         //bug(
31         int k=qu(m,R);
32         //ans=m;
33         if(k==res)l=m;
34         else r=m;
35     }
36     cout<<"! "<<l<<endl;
37 }
38 
39 int gao2(int L,int R){
40     int l=L,r=R,m=L;
41     while(l<r-1){
42         m=(l+r)/2;
43         int k=qu(L,m);
44         if(k==res)r=m;
45         else l=m;
46     }
47     cout<<"! "<<r<<endl;
48 }
49 
50 int main(){
51     cin>>n;
52     res=qu(1,n);
53     int res1=-1,res2=-1;
54     if(res>1)res1=qu(1,res);
55     if(res<n)res2=qu(res,n);
56     if(res1==res)gao1(1,res);
57     else gao2(res,n);
58 }
59 /*
60 5
61 3
62 3
63 5
64 3
65 
66 *2
67 
68 5
69 3
70 3
71 5
72 2
73 *1
74 */