Submission #1227181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227181		brinton	Rarest Insects (IOI22_insects)	C++20	57.14 / 100	45 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
  auto tryk = [&](int k){
    vector<int> cur;
    for(int i = 0;i < N;i++){
      move_inside(i);
      if(press_button() > k){
        move_outside(i);
      }else{
        cur.push_back(i);
      }
    }
    for(auto &i:cur) move_outside(i);
    return cur.size();
  };
  // first check group
  int gp = tryk(1);
  if(gp <= 8){
    int ans = N;
    vector<int> vis(N,false);
    for(int t = 0;t < gp;t++){
      vector<int> cur;
      for(int i = 0;i < N;i++){
        if(vis[i]) continue;

        move_inside(i);
        if(press_button() > cur.size()){
          cur.push_back(i);
        }else{
          move_outside(i);
        }
      }
      for(auto &i:cur) vis[i] = true;
      for(auto &i:cur) move_outside(i);
      ans = min(ans,(int)cur.size());
    }
    return ans;
  }
  // binary search
  int bottom = 1;
  int top = N/gp;
  int maxPossible = 1;
  while(bottom <= top){
    int mid = (bottom+top)/2;
    int respond = tryk(mid);
    if(respond == gp*mid){
      maxPossible = max(maxPossible,mid);
      bottom = mid+1;
    }else{
      top = min(respond/gp,mid-1);
    }
  }
  return maxPossible;
}

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