Submission #1211494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211494		mychecksedad	Rarest Insects (IOI22_insects)	C++17	100 / 100	15 ms	440 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();


  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];
        if(mid * sz == inside){
          last_pres = mid;
          U.pb(x);
        }else{
          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];
        if(inside == mid * sz){
          last_pres = mid;
          u.pb(x);
        }else{
          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: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75