제출 #1211465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211465		mychecksedad	Rarest Insects (IOI22_insects)	C++17	47.50 / 100	60 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;


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

  int l = 1, r = n / sz, ans = r;
  while(l <= r){
    int mid = l+r>>1;
    // u is the cur search set.
    vi cc;
    for(int x: u){
      move_inside(x);
      if(press_button() > mid){
        move_outside(x);
      }else cc.pb(x);  
    }
    for(int x: cc) move_outside(x);
    if(cc.size() == mid * sz){
      ans = mid;
      l = mid + 1;
    }else{
      r = mid - 1;
    }

  }

  return ans;
}

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