SHARE
TWEET

Untitled

a guest Jun 22nd, 2019 264 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <functional>
  4. #include <numeric>
  5. #include <random>
  6. #include <map>
  7. using namespace std;
  8. #define int long long
  9. const int FSZ = 1e18;
  10. mt19937 rnd;
  11. int cntq=0;
  12. int ask(int id, int x) {
  13.     cout << "? " << id + 1 << " " << x << endl;
  14.     int ans;
  15.     cin >> ans;
  16.     ++cntq;
  17.     return ans;
  18. }
  19. int n, L, value;
  20. vector<pair<int, int> > ans;
  21. int bs(int guy, int val, int l, int r){
  22.     int ll=l, rr=r;
  23.     while (rr - ll > 1){
  24.         int mm = (ll+rr)/2;
  25.         int res = ask(guy, mm);
  26.         if (res == val) return mm;
  27.         if (res < val) ll = mm;
  28.         else rr = mm;
  29.     }
  30. }
  31. pair<vector<int>, vector<int> > kth(vector<int> men, int as, int K, int l, int r){
  32.     if (men.size() == 1){
  33.         return {men, {}};
  34.     }
  35.     int R = rnd() % men.size();
  36.     vector<int> left, eql, right;
  37.     int V = bs(men[R], (L/n)*as, l, r);
  38.     eql.push_back(men[R]);
  39.     int C = (L/n)*as;
  40.     for (int i=0; i < men.size(); i++){
  41.         if (i==R) continue;
  42.         int T = ask(men[i], V);
  43.         if (T < C) right.push_back(men[i]);
  44.         if (T == C) eql.push_back(men[i]);
  45.         if (T > C) left.push_back(men[i]);
  46.     }
  47.     while (left.size() < K && eql.size()){
  48.         left.push_back(eql.back());
  49.         eql.pop_back();
  50.     }
  51.     if (left.size() == K){
  52.         value = V;
  53.         while (eql.size()){
  54.             right.push_back(eql.back());
  55.             eql.pop_back();
  56.         }
  57.         return {left, right};
  58.     }
  59.     if (left.size() < K){
  60.         pair<vector<int>, vector<int> > p = kth(right, as, K-left.size(), l, r);
  61.         while (left.size()){
  62.             p.first.push_back(left.back());
  63.             left.pop_back();
  64.         }
  65.         return p;
  66.     }
  67.     while (eql.size()){
  68.         right.push_back(eql.back());
  69.         eql.pop_back();
  70.     }
  71.     pair<vector<int>, vector<int> > p = kth(left, as, K, l, r);
  72.     while (right.size()){
  73.         p.second.push_back(right.back());
  74.         right.pop_back();
  75.     }
  76.     return p;
  77. }
  78. void divide(int start, int l, int r, vector<int> men){
  79.     if (men.size() == 1){
  80.         ans[men[0]] = {l, r};
  81.         return;
  82.     }
  83.     int F = men.size() / 2;
  84.     int as = start+F;
  85.     pair<vector<int>, vector<int> > p = kth(men, as, F, l, r);
  86.     int V = value;
  87.     divide(start, l, V, p.first);
  88.     divide(start+p.first.size(), V, r, p.second);
  89. }
  90. signed main() {
  91.     //ios_base::sync_with_stdio(false);
  92.     cin >> n >> L;
  93.     vector<int> men;
  94.     for (int i=0; i < n;i++) men.push_back(i);
  95.     ans.assign(n, {-1, -1});
  96.     divide(0, 0, FSZ, men);
  97.     cout << "!" << endl;
  98.     for (int i = 0; i < n; ++i)
  99.         cout << ans[i].first << " " << ans[i].second << endl;
  100.     cerr << "Done " << cntq << " queries\n";
  101.     return 0;
  102. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top