fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <bits/extc++.h> /** keep-include */
  3. using namespace __gnu_pbds;
  4.  
  5. using namespace std;
  6. #define int long long
  7.  
  8. template<class T>
  9. using Tree = tree<T, null_type, less<T>, rb_tree_tag,
  10.     tree_order_statistics_node_update>;
  11.  
  12. using vi = vector<int>;
  13.  
  14.  
  15. int query(int a, int b) {
  16. 	cout<<"? "<<a<<" "<<b<<endl;
  17. 	cout.flush();
  18. 	int x;
  19. 	cin>>x;
  20. 	return x;
  21. }
  22.  
  23. void solve() {
  24. 	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25. 	int n;
  26. 	cin>>n;
  27. 	Tree<int> t;
  28. 	for(int i=1;i<=(1<<n);i++) {
  29. 		t.insert(i);
  30. 	}
  31. 	int qr = (1 << (n + 1))/3;
  32. 	int candidate = 1;
  33. 	t.erase(candidate);
  34. 	while(t.size() > 0 && qr--) {
  35. 		int sz = t.size();
  36. 		int kth = rng()%sz;
  37. 		int maybe = *t.find_by_order(kth);
  38. 		t.erase(maybe);
  39. 		if(!query(candidate, maybe)) {
  40. 			candidate = maybe;
  41. 		}
  42. 	}
  43. 	cout<<"! "<<candidate<<endl;
  44.  
  45. }
  46.  
  47. int32_t main() {
  48. 	int t = 1;
  49. 	cin>>t;
  50. 	while(t--) solve();
  51. }
  52.  
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
! 1
https://ideone.com/iPPrDa
language:
C++14 (gcc 8.3)
created:
1 year 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!