제출 #1227179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227179		brinton	Rarest Insects (IOI22_insects)	C++20	47.50 / 100	59 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);
  // binary search
  int bottom = 1;
  int top = N;
  int maxPossible = 1;
  // cout << "!" << gp << endl;
  while(bottom <= top){
    int mid = (bottom+top)/2;
    int respond = tryk(mid);
    // cout << bottom << " " << top << endl;
    // cout << "!" << mid << ":" << respond << endl;
    if(respond == gp*mid){
      maxPossible = max(maxPossible,mid);
      bottom = mid+1;
    }else{
      top = min(respond/gp,mid-1);
    }
  }
  // cout << bottom << " " << top << endl;
  return maxPossible;
}

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