Advertisement
vlatkovski

toki open day 0 c

Jul 1st, 2019
405
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int, int> pii;
  5.  
  6.  
  7. vector<int> ask(vector<int> v) {
  8.     cout << "? " << v.size() << " ";
  9.     for (int x : v) cout << x << ' ';
  10.     cout << endl;
  11.     vector<int> res;
  12.     int sz;
  13.     cin >> sz;
  14.     while (sz--) {
  15.         int x;
  16.         cin >> x;
  17.         res.push_back(x);
  18.     }
  19.     return res;
  20. }
  21.  
  22. int main() {
  23. //    ios::sync_with_stdio(false); cin.tie(0);
  24.     int N, M, Q;
  25.     cin >> N >> M >> Q;
  26. //    if (N+M <= Q) {
  27. //        for (int i = 1; i <= N+M; ++i) {
  28. //            vector<int> res = ask({i});
  29. //            if (res.empty() || res.size() > 1) {
  30. //                cout << "! " << i << endl;
  31. //                return 0;
  32. //            }
  33. //        }
  34. //    } else {
  35.         vector<int> nodes, res;
  36.         for (int i = 1; i <= N+M; ++i) {
  37.             nodes.push_back(i);
  38.         }
  39.         res = ask(nodes);
  40.         if (res.size() < N+M) {
  41.             vector<bool> had(N+M+1, false);
  42.             for (int x : res) {
  43.                 had[x] = true;
  44.             }
  45.             for (int i = 1; i <= N+M; ++i) {
  46.                 if (had[i] == false) {
  47.                     cout << i << endl;
  48.                     return 0;
  49.                 }
  50.             }
  51.         }
  52.         int L1 = 1, R1 = N, L2 = N+1, R2 = N+M, m1, m2;
  53.         while (L1+1 <= R1 || L2+1 <= R2) {
  54.             nodes.clear();
  55.             res.clear();
  56. //            cout << "L1=" << L1 << " R1=" << R1 << " L2=" << L2 << " R2=" << R2 << endl;
  57.             if (L1+1 <= R1) {
  58.                 m1 = (L1 + R1) / 2;
  59.                 for (int i = L1; i <= m1; ++i) {
  60.                     nodes.push_back(i);
  61.                 }
  62.             }
  63.             if (L2+1 <= R2) {
  64.                 m2 = (L2 + R2) / 2;
  65.                 for (int i = L2; i <= m2; ++i) {
  66.                     nodes.push_back(i);
  67.                 }
  68.             }
  69.             res = ask(nodes);
  70.             vector<int> res1, res2;
  71.             for (int x : res) {
  72.                 if (x <= N) {
  73.                     res2.push_back(x);
  74.                 } else {
  75.                     res1.push_back(x);
  76.                 }
  77.             }
  78.             if (L1+1 <= R1) {
  79.                 if (res1.size() != m1-L1+1) {
  80.                     R1 = m1;
  81. //                    cout << "(1) " << res1.size() << " > " << m1-L1+1 << " ==> R1=" << m1 << endl;
  82.                 } else {
  83.                     L1 = m1+1;
  84. //                    cout << "(1) " << res1.size() << " = " << m1-L1+1 << " ==> L1=" << m1+1 << endl;
  85.                 }
  86.             }
  87.             if (L2+1 <= R2) {
  88.                 if (res2.size() != m2-L2+1) {
  89.                     R2 = m2;
  90.                 } else {
  91.                     L2 = m2+1;
  92.                 }
  93.             }
  94.         }
  95.         cout << "! ";
  96.         if (L1 == R1) {
  97.             cout << L1 << endl;
  98.         } else {
  99.             cout << L2 << endl;
  100.         }
  101. //    }
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement