Submission #1328207

#TimeUsernameProblemLanguageResultExecution timeMemory
1328207SmuggingSpunColors (BOI20_colors)C++20
100 / 100
1 ms436 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool ask(ll x){
  cout << "? " << x << endl;
	int k;
  cin >> k;
  return k == 1;
}
ll n;
namespace sub1{
	void solve(){
		ask(1);
		for(int i = n, cur = 1; i > 1; i--){
			if((n ^ i ^ 1) & 1){
				if(!ask(cur += i - 1)){
					return void(cout << "= " << i); 
				}
			}
			else if(!ask(cur -= i - 1)){
				return void(cout << "= " << i);
			}
		}
		cout << "= 1";
	}
}
namespace sub2345{
  void solve(){
    vector<ll>a;
    ll low = 1, high = n - 1, ans = n;
    while(low <= high){
      ll mid = (low + high) >> 1LL;
      a.push_back(mid);
      low = mid + 1;
    }
    reverse(a.begin(), a.end());
    int sign = 1;
    ll p = 1;
    for(ll& x : a){
      p += x * sign;
      sign = -sign;
    }
    ask(p);
    for(low = 1, high = n - 1; low <= high; sign = -sign){
      ll mid = (low + high) >> 1LL;
      if(ask(p += mid * sign)){
        high = (ans = mid) - 1;
      }
      else{
        low = mid + 1;
      }
    }
    cout << "= " << ans;
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	if(n <= 64){
		sub1::solve();
	}
  else{
    sub2345::solve();
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...