fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define F               first
  5. #define S               second
  6. #define mp              make_pair
  7.  
  8. #define pb(v,x)         v.push_back(x)
  9. #define ins(s, x)       s.insert(x)
  10.  
  11. #define nl              cout<<endl
  12. #define no              cout<<"No"<<endl
  13. #define yes             cout<<"Yes"<<endl
  14. #define mone            cout<<"-1"<<endl
  15. #define zero            cout<<"0"<<endl
  16.  
  17. #define incs(v)         sort(v.begin(), v.end())
  18. #define rev(s)          reverse(s.begin(), s.end())
  19. #define ps(x, cmp)      sort(x.begin(),x.end(),cmp)
  20. #define onesll(x)       __builtin_popcountll(x)
  21. #define trailZero(x)    __builtin_ctzll(x)
  22. #define checkSort(v)    is_sorted(v.begin(), v.end())
  23.  
  24. #define f(i,k,n)        for(ll i = k; i < n ;i ++)
  25. #define fr(i, k, l)     for(ll i = k - 1; i >= l; i--)
  26. #define fsq(i, j, k)    for(ll i = j; i * i <= k; i ++)
  27. #define fm(val, m)      for(auto val : m)
  28.  
  29. #define freq(v,num)     count(v.begin(), v.end(), num)
  30. #define max_vect(v)     *max_element(v.begin(), v.end())
  31. #define min_vect(v)     *min_element(v.begin(), v.end())
  32. #define sum_vect(v)     accumulate(v.begin(), v.end(), 0LL)
  33. #define consec(v, l)    iota(v.begin(), v.end(), l);
  34. #define all(v)          v.begin(), v.end()
  35. #define srch(v, x)      find(v.begin(), v.end(), x)
  36. #define rot(v, x)       rotate(v.begin(), v.begin() + x, v.end());
  37. #define lob(v, x)       lower_bound(v.begin(), v.end(), x)
  38. #define ub(v, x)        upper_bound(v.begin(), v.end(), x)
  39. #define permute(v)      next_permutation(v.begin(), v.end())
  40.  
  41. #define vpll            vector <pair<long long,long long>>
  42. #define vll             vector<long long>
  43. #define vvll            vector<vector<long long>>
  44. #define vs              vector<string>
  45.  
  46. #define mll             map<long long,long long>
  47. #define msl             map<string, long long>
  48. #define mcl             map<char, long long>
  49.  
  50. #define sl              set<long long>
  51. #define ss              set<string>
  52.  
  53. #define cout(v)         for(ll i = 0 ; i < v.size(); i ++) {cout<<v[i]<<" ";}
  54. #define coutp(v)        for(ll i = 0 ; i < v.size(); i ++) {cout<<v[i].F<<" "<<v[i].S<<endl;}
  55.  
  56. #define w(t)            long long t; cin>>t; while(t--)
  57. #define fast_io         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  58.  
  59. #define llmax           LLONG_MAX
  60. #define llmin           LLONG_MIN
  61.  
  62. typedef long double     ld;
  63. typedef double          db;
  64. typedef long long       ll;
  65.  
  66. const ll mod =          998244353;
  67. const ll MOD =          1e9 + 7;
  68. const ll Inf =          999999937;
  69. const db pi =           3.1415926535897932384626;
  70. const ll P =            31;
  71. const ll N =            1e7 + 10;
  72.  
  73. /* 2d Vector Input------------------------------------------------------------------------------------- */
  74.  
  75. void input2d(vvll &v, ll n, ll m) {
  76.     ll x;
  77.     f(i, 0, n) {
  78.         vll u;
  79.         f(j, 0, m) {
  80.                 cin >> x; pb(u, x);
  81.         }
  82.         pb(v, u);
  83.     }
  84. }
  85.  
  86. /* 1d Vector Input------------------------------------------------------------------------------------- */
  87.  
  88. void input(vll &v, ll n) {
  89.     ll x;
  90.     f(i, 0, n) {
  91.             cin >> x; pb(v, x);
  92.     }
  93. }
  94.  
  95. /* Vector Pair Input------------------------------------------------------------------------------------- */
  96.  
  97. void inputp(vpll &v, ll n) {
  98.     ll x, y;
  99.     f(i, 0, n) {
  100.             cin >> x >> y; pb(v, mp(x, y));
  101.     }
  102. }
  103.  
  104. /* Binary Exponentiation------------------------------------------------------------------------------- */
  105.  
  106. ll pw(ll a, ll b, ll mod = MOD) {
  107.     ll y;
  108.     if (!a) return 0; 
  109.     if (!b) return (1 + mod) % mod; 
  110.     if(b & 1) y = ((a % mod) * (pw(a, b - 1, mod) % mod)) % mod; 
  111.     else { 
  112.             y = pw(a, b / 2, mod); 
  113.             y = ((y % mod) * (y % mod)) % mod;
  114.     } 
  115.     return (y + mod) % mod; 
  116. }
  117.  
  118. /*LCM of Array__O(n * log(min(a, b)))------------------------------------------------------------------ */
  119.  
  120. ll lcm(vll &v) {
  121.     ll n = v.size(), ans = v[0];
  122.     f(i, 1, n)ans = (v[i] * ans) / __gcd(v[i], ans);
  123.     return ans;
  124. }
  125.  
  126. /* Seive__Algorithm__O(n * log(log N))----------------------------------------------------------------- */
  127. vll seive;
  128.  
  129. void create() {
  130.     seive.resize (N + 1);
  131.  
  132.     f (i, 0, N + 1) seive[i] = i;
  133.     seive[0] = seive[1] = 1e9;
  134.  
  135.     for(ll i = 2; i * i <= N; i ++) {
  136.         if(seive[i] == i) {
  137.             for(ll j = i * i; j <= N; j += i) {
  138.                 if (seive[j] == j) seive[j] = i;
  139.             }
  140.         }
  141.     }
  142. }
  143.  
  144. /*----------------------------------------------------------------------------------------------------- */
  145. void solve () {
  146.     ll n; cin >> n;
  147.  
  148.     set <ll> st;
  149.     f (i, 1, n + 1) ins (st, i);
  150.  
  151.     vll v (n + 1, 0);
  152.  
  153.     ll ct = 0, ans = 0;
  154.     while (ct < 10) {
  155.         ll o = 0, z;
  156.         mll m;
  157.         fm (val, st) {
  158.             cout << "? " << val << " 1" << endl;
  159.             ll x; cin >> x;  
  160.             if (x) {
  161.                 o ++; m[val] ++;
  162.             }
  163.         }
  164.  
  165.         z = st.size () - o;
  166.         ll x = (1 << ct);
  167.         o = (o + x - 1) / x; z = (z + x - 1) / x;
  168.         if (o == z) {
  169.             if (z % x == 0) {
  170.                 ans += (1 << ct);
  171.                 fm (val, m) if (val.S == 1) st.erase (val.S);
  172.             }
  173.             else {
  174.                 fm (val, m) if (val.S == 0) st.erase (val.S);
  175.             }
  176.         }
  177.         else {
  178.             if (o % x == 0) {
  179.                 fm (val, m) if (val.S == 0) st.erase (val.S);
  180.             }
  181.             else {
  182.                 ans += (1 << ct);
  183.                 fm (val, m) if (val.S == 1) st.erase (val.S);
  184.             }
  185.         }
  186.  
  187.         cout << st.size () << endl;
  188.  
  189.         ct ++;
  190.     }
  191. }
  192.  
  193. int main() {
  194.     fast_io;
  195.  
  196.     int t; cin >> t;
  197.     for (int i = 1; i <= t; i ++) {
  198.         solve ();
  199.     }
  200.  
  201.     return 0;
  202. }
  203.  
  204. /*----------------------------------------------------------------------------------------------------- */
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
2
stdout
copy 
? 1 1
? 2 1
2
? 1 1
? 2 1
1
? 2 1
1
? 2 1
1
? 2 1
1
? 2 1
1
? 2 1
1
? 2 1
1
? 2 1
1
? 2 1
1
https://ideone.com/SJLUkz
language:
C++14 (gcc 8.3)
created:
10 days 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!