fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false) ; cin.tie(NULL)
  4.  
  5. const int INF= 1e6 + 7;
  6. const int N = 1e5 + 7;
  7. int a[N] , n;
  8. void inp(){
  9.     cin >> n;
  10. }
  11.  
  12. int ask(int id){
  13.     if (id < 1 || id > n) return INF;
  14.     if (a[id] != 0) return a[id];
  15.  
  16.     cout << "? " << id << '\n';
  17.     cout.flush();
  18.  
  19.     int res;
  20.     cin >> res;
  21.     a[id] = res;
  22.     return a[id];
  23. }
  24.  
  25. void solve(){
  26.     int l = 1 , r = n , mid;
  27.     while (l <= r){
  28.         mid = (l + r) >> 1;
  29.         int Mid = ask(mid) , L = ask(mid - 1) , R = ask(mid + 1);
  30.         if (Mid < L && Mid < R){
  31.             cout << "! " << mid << '\n';
  32.             cout.flush();
  33.             return;
  34.         }
  35.         if (Mid > L){
  36.             r = mid - 1;
  37.         }
  38.         else if (Mid > R){
  39.             l = mid + 1;
  40.         }
  41.     }
  42. }
  43.  
  44. int main(){
  45.     faster;
  46.     inp();
  47.     solve();
  48.     return 0;
  49. }
  50.  
  51.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/k1N4Tf
language:
C++14 (gcc 8.3)
created:
10 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!