Advertisement
YEZAELP

o62_mar_c1_socks

Jan 19th, 2022
389
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// Interactive
  2. #include "sockslib.h"
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. const int inf = 1e9;
  7. const int N = 2e3 + 10;
  8. bool in[N];
  9. int k, n;
  10.  
  11. bool Check(int s, int e, int cnt = 0){
  12.     vector <int> socks;
  13.     for(int i=s;i<=e;i++){
  14.         if(in[i])
  15.             socks.push_back(i), cnt ++;
  16.     }
  17.     return ask(socks) < cnt;
  18. }
  19.  
  20. int main() {
  21.     n = 2 * num();
  22.     for(int i=1;i<=2*n;i++) in[i] = true;
  23.  
  24.     for(int i=1;i<=n;i++){
  25.         int l = 1, r = i, mx = -inf;
  26.         while(l <= r){
  27.             int mid = (l + r) / 2;
  28.             if(Check(mid, i))
  29.                 l = mid + 1, mx = max(mx, mid);
  30.             else
  31.                 r = mid - 1;
  32.         }
  33.         if(mx != -inf){
  34.             in[i] = in[mx] = false;
  35.             match(i, mx);
  36.         }
  37.     }
  38.  
  39.     return 0;
  40. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement