Advertisement
Guest User

Untitled

a guest
Dec 20th, 2019
636
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.29 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. #define rep(i, a, b) for(int i=(a); i<(b); i++)
  5. #define repi(i, a, b) for(int i=(a); i>(b); i--)
  6. #define db(x) (cerr << #x << ": " << (x) << '\n')
  7. #define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
  8. #define cps CLOCKS_PER_SEC
  9. #define tests(t) int t; cin >> t; while(t--)
  10. #define iceil(n, x) (((n) + (x) - 1) / (x))
  11. #define ll long long
  12. #define gcd __gcd
  13. #define eb emplace_back
  14. #define pb push_back
  15. #define pf push_front
  16. #define pob pop_back
  17. #define pof pop_front
  18. #define sz size()
  19. #define all(v) (v).begin(), (v).end()
  20. #define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
  21. #define pii pair<int, int>
  22. #define vi vector<int>
  23. #define vpii vector<pii>
  24. #define vvi vector<vi>
  25. #define fi first
  26. #define se second
  27. #define mt make_tuple
  28. #define pqueue priority_queue
  29. #define bitcount(x) __builtin_popcount(x)
  30. #define PI acos(-1.0)
  31. #define EPS 1e-9
  32. #define mod 1000000007
  33. using namespace std;
  34.  
  35. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  36. template <typename Arg1>
  37. void __f(const char* name, Arg1&& arg1){
  38. cerr << name << " : " << arg1 << '\n';
  39. }
  40. template <typename Arg1, typename... Args>
  41. void __f(const char* names, Arg1&& arg1, Args&&... args){
  42. const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  43. }
  44.  
  45. template<typename T1, typename T2>
  46. ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << '(' << p.fi << ", " << p.se << ')'; }
  47.  
  48. template<typename T>
  49. void printv(const T& v) { for(auto i : v) cerr << i << ' '; cerr << '\n'; }
  50.  
  51. template<typename T>
  52. using minpq = priority_queue<T, vector<T>, greater<T>>;
  53.  
  54. template<typename T>
  55. using maxpq = priority_queue<T>;
  56.  
  57. //All indexing is 0-based
  58. using namespace __gnu_pbds;
  59. template<class key, class cmp = std::less<key>>
  60. using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  61. //methods: find_by_order(k); & order_of_key(k);
  62. //To make it an ordered_multiset, use pairs of (value, time_of_insertion)
  63. //to distinguish values which are similar
  64.  
  65. template<class key, class value, class cmp = std::less<key>>
  66. using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
  67.  
  68. //Returns no. of values x for which ceil(n / x) == y (y must be > 1).
  69. inline ll CC(ll n, ll y) { return iceil(n, y-1) - iceil(n, y); }
  70.  
  71. //Returns no. of values x for which floor(n / x) == y
  72. inline ll FF(ll n, ll y) { return n / y - n / (y+1); }
  73.  
  74. //a and b are assumed to be taken modulo p
  75. inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c; }
  76. inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c; }
  77. inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p; }
  78.  
  79. #define N 100005
  80. #define int ll
  81. // #define trace(...) 42
  82.  
  83. int n, b;
  84.  
  85. inline bool bit(int n, int b) {
  86. return (n >> b) & 1;
  87. }
  88.  
  89. int solve() {
  90. cout << 2 << ' ' << 1 << ' ' << n << endl;
  91. int x; cin >> x;
  92. if(!x) {
  93. return -1;
  94. }
  95.  
  96. for(b = 31; b; b--) {
  97. if(bit(x, b)) break;
  98. }
  99.  
  100. // trace(b);
  101.  
  102. // int lo = 1, hi = n-1, ans = n;
  103. // while(lo <= hi) {
  104. // int md = (hi + lo) / 2;
  105. // cout << 1 << ' ' << 1 << ' ' << md << endl;
  106.  
  107. // int val; cin >> val;
  108.  
  109. // if(bit(val, b)) {
  110. // ans = min(ans, md);
  111. // hi = md - 1;
  112. // }
  113. // else {
  114. // lo = md + 1;
  115. // }
  116. // }
  117.  
  118. int lo = 0, hi = n;
  119. while(hi - lo > 1) {
  120. int md = (hi + lo) / 2;
  121. cout << 1 << ' ' << 1 << ' ' << md << endl;
  122. int val; cin >> val;
  123. if(bit(val, b)) hi = md;
  124. else lo = md;
  125. }
  126.  
  127. int ans = hi;
  128.  
  129. if(ans == n) ans = -1;
  130. return ans;
  131. }
  132.  
  133. main()
  134. {
  135. #ifdef CP
  136. // freopen("/home/tarun/Desktop/input.txt", "r", stdin);
  137. // freopen("/home/tarun/Desktop/output.txt", "w", stdout);
  138. #endif
  139. // sync;
  140. clock_t clk = clock();
  141. cerr << "I will return...\n";
  142.  
  143. cin >> n;
  144. ll ans=solve();
  145. cout << "! " << ans<< endl;
  146.  
  147. cerr << "...don't you ever hang your head.\n";
  148. cerr << "Time (in ms): " << (double)(clock() - clk) * 1000.0 / cps << '\n';
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement