fork download 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define ld long double
  6. #define eb emplace_back
  7. #define ef emplace_front
  8. #define pii pair <int, int>
  9. #define pli pair <ll, int>
  10. #define pll pair <ll, ll>
  11. #define pci pair <char, int>
  12. #define pil pair <int, ll>
  13. #define pic pair <int, char>
  14. #define fi first
  15. #define se second
  16. #define all(ac) ac.begin(), ac.end()
  17. #define MASK(x) (1 << (x))
  18. #define ub(i, j) ((i >> j) & 1)
  19. #define FBIT(x) (MASK(x) - 1)
  20. #define FLIP(x, y) (FBIT(x) ^ y)
  21. #define bit_count(x) (int) (__builtin_popcount(x))
  22. #define bit_countll(x) (int) (__builtin_popcountll(x))
  23. #define ii make_pair
  24. #define int128 __int128_t
  25. #define SZ(x) ((int) x.size())
  26. #define multi 0
  27.  
  28. const int MX = 1002;
  29. int n, k;
  30. int winner[MX][MX];
  31.  
  32. bool mimeo = 0;
  33.  
  34. int ask(int x, int y) {
  35.     if(!winner[x][y]) {
  36.         cout << "? " << x << ' ' << y << endl;
  37.         cin >> winner[x][y], winner[y][x] = winner[x][y];
  38.     }
  39.     return winner[x][y];
  40. }
  41.  
  42. struct segtree {
  43.     int n;
  44.     vector <int> tree;
  45.  
  46.     segtree(int n = 0): n(n), tree(n << 2 | 1, 0) {}
  47.  
  48.     int Merge(int x, int y) {
  49.         if(!x || !y) return x + y;
  50.  
  51.         int t = ask(x, y);
  52.         if(!mimeo) return t;
  53.         return t == x ? y : x;
  54.     }
  55.  
  56.     void Build(int id, int l, int r) {
  57.         if(l == r) return void(tree[id] = l);
  58.  
  59.         int mid = (l + r) >> 1;
  60.  
  61.         Build(id << 1, l, mid);
  62.         Build(id << 1 | 1, mid + 1, r);
  63.  
  64.         tree[id] = Merge(tree[id << 1], tree[id << 1 | 1]);
  65.         return;
  66.     }
  67.  
  68.     void update(int id, int l, int r, int pos) {
  69.         if(l > pos || r < pos) return;
  70.         if(l == r) return void(tree[id] = 0);
  71.  
  72.         int mid = (l + r) >> 1;
  73.  
  74.         update(id << 1, l, mid, pos);
  75.         update(id << 1 | 1, mid + 1, r, pos);
  76.  
  77.         tree[id] = Merge(tree[id << 1], tree[id << 1 | 1]);
  78.         return;
  79.     }
  80.  
  81.     void Build() {
  82.         return Build(1, 1, n), void();
  83.     }
  84.  
  85.     void update(int pos) {
  86.         return update(1, 1, n, pos), void();
  87.     }
  88. } smt;
  89.  
  90. void solve() {
  91.     cin >> n >> k;
  92.  
  93.     if(k == n) {
  94.         cout << "! 1 1" << endl;
  95.         for(int i = 1; i <= n; i++) cout << i << ' ';
  96.         return;
  97.     }
  98.  
  99.     if(k == 1) {
  100.         int res = 1;
  101.         for(int i = 2; i <= n; i++) res = ask(res, i);
  102.         cout << "! 1 1" << endl;
  103.         cout << res;
  104.         return;
  105.     }
  106.  
  107.     if(k > n - k) {
  108.         k = n - k;
  109.         mimeo = 1;
  110.     }
  111.  
  112.     if(k > 40) {
  113.         vector <int> a(n);
  114.         iota(all(a), 1);
  115.  
  116.         mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  117.         shuffle(all(a), rng);
  118.  
  119.         auto cmp = [&] (const int &x, const int &y) -> bool {
  120.             if(x == y) return 0;
  121.             return ask(x, y) == x && !mimeo || ask(x, y) == y && mimeo;
  122.         };
  123.  
  124.         nth_element(a.begin(), a.begin() + k, a.end(), cmp);
  125.  
  126.         cout << "! 1 1" << endl;
  127.  
  128.         if(!mimeo) {
  129.             for(int i = 0; i < k; i++) cout << a[i] << ' ';
  130.         }
  131.         else {
  132.             for(int i = k; i < n; i++) cout << a[i] << ' ';             
  133.         }
  134.         return;
  135.     }
  136.  
  137.     smt = segtree(n);
  138.     smt.Build();
  139.  
  140.     vector <int> res;
  141.     for(int i = 1; i <= k; i++) {
  142.         res.eb(smt.tree[1]);
  143.         if(i < k) smt.update(res.back());
  144.     }
  145.  
  146.     cout << "! 1 1" << endl;
  147.  
  148.     if(mimeo) {
  149.         vector <bool> vis(n + 1, 0);
  150.         for(int &i : res) vis[i] = 1;
  151.         for(int i = 1; i <= n; i++) if(!vis[i]) {
  152.             cout << i << ' ';
  153.         }
  154.     }
  155.     else {
  156.         for(int &i : res) cout << i << ' ';
  157.     }
  158.     return;
  159. }
  160.  
  161. int32_t main() {
  162.     ios::sync_with_stdio(false);
  163.     cin.tie(0), cout.tie(0);
  164.     #define task "tet"
  165.     if(fopen(task".inp", "r")) {
  166.         freopen(task".inp", "r", stdin);
  167.         freopen(task".out", "w", stdout);
  168.     }
  169.  
  170.     int testcase = multi == 2 ? 1e9 : 1; if(multi == 1) cin >> testcase;
  171.     while(testcase--) solve();
  172.     return 0;
  173. }
  174.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin 
Standard input is empty
stdout 
! 1 1
https://ideone.com/e8puAx
language:
C++ (gcc 8.3)
created:
1 day 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!