제출 #1211487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211487		mychecksedad	드문 곤충 (IOI22_insects)	C++17	0 / 100	15 ms	432 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define en cout << '\n'
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
const int N = 1e5+10;

mt19937 rng(2342352342);

int rn(int l, int r){
  return uniform_int_distribution<int>(l,r)(rng);
}

int last_pres = 0;
int press_buttoon(){
  return last_pres = press_button();
}

int min_cardinality(int n) {
  vi v, u;
  vi ord;
  for(int i = 1; i <= n; ++i){
    ord.pb(i-1);
    swap(ord[i-1], ord[rn(0,i-1)]);
  }
  for(int j = 0; j < n; ++j){
    int i = ord[j];
    move_inside(i);
    int val = press_button();
    if(val > 1){
      move_outside(i);
      u.pb(i);
    }else{
      v.pb(i);
    }
    // u.pb(i);
  }
  // for(int x: v) move_outside(x);
  int sz = v.size();

  if(sz <= 4){
    int l = 2, r = 4, ans = 1;
    for(int x: v) move_outside(x);
    while(l <= r){
      int mid = l+r>>1;
      int inside = 0;
      vi nxt;
      for(int j = 0; j < n; ++j){
        move_inside(j);
        if(press_button() <= mid){
          ++inside;
          nxt.pb(j);
        }else{
          move_outside(j);
        }
      }
      for(int x: nxt) move_outside(x);
      if(inside == sz * mid){
        ans = mid;
        l = mid + 1;
      }else{
        r = mid - 1;
      }
    }

    return ans;
  }

  // v.clear();

  last_pres = 1;

  int l = 2, r = n / sz, ans = 1;
  int inside = sz;
  while(l <= r){
    int mid = l+r>>1;
    // u is the cur search set, v is the inside set.

    if(last_pres <= mid){
      // we gotta add new ones from u.
      // the ones in v are fixed.
      v.clear();
      vi U;
      if(u.size()){
        move_inside(u[0]);
        v.pb(u[0]);
        ++inside;
      }
      for(int j = 1; j < u.size(); ++j){
        int x = u[j];
        move_inside(x);
        if(press_buttoon() <= mid){
          v.pb(x);
          ++inside;
        }else{
          last_pres = mid;
          move_outside(x);
          U.pb(x);
        }
      }
      u = U;
    }else{
      // we gotta erase some from v.
      u.clear();
      for(int j = 0; j + 1 < v.size(); ++j) move_outside(v[j+1]), --inside;
      vi V;
      V.pb(v[0]);
      for(int j = 1; j < v.size(); ++j){
        int x = v[j];
        move_inside(x);
        if(press_buttoon() <= mid){
          V.pb(x);
          ++inside;
        }else{
          last_pres = mid;
          u.pb(x);
          move_outside(x);
        }
      }
      v = V;
    }
    // cerr << l << ' ' << r << " :\n";
    // for(int x: v) cerr << x << ' ';  cerr << '\n';
    // for(int x: u) cerr << x << ' ';  cerr << '\n';
    // cerr << '\n';
    if(inside == mid * sz){
      ans = mid;
      l = mid + 1;
    }else{
      r = mid - 1;
    }

  }

  return ans;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75