제출 #1211485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211485		mychecksedad	드문 곤충 (IOI22_insects)	C++17	99.89 / 100	15 ms	444 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 <= 2){
    for(int x: v) move_outside(x);
    vector<int> tp(n, -1);
    for(int j = 0; j < v.size(); ++j) tp[v[j]] = j;
    for(int i = 0; i < n; ++i){
      if(tp[i] != -1) continue;
      tp[i] = 0;
      move_inside(i);
      for(int j = 1; j < v.size(); ++j){
        move_inside(v[j]);
        if(press_button() == 2){
          tp[i] = j;
          move_outside(v[j]);
          break;
        }
        move_outside(v[j]);
      }
      move_outside(i);
    }
    array<int, 3> res = {0};
    for(int x: tp) res[x]++;
    int ans = 1e9;
    for(int j = 0; j < sz; ++j) ans = min(ans, res[j]);
    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: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 74.89 / 75