제출 #1248957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1248957		pcp	드문 곤충 (IOI22_insects)	C++20	45.45 / 100	65 ms	508 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;


int getnum(int N, int   M){
  set<int> in;
  int lr = 0;
  for (int i = 0 ; i < N ; ++i){

    move_inside(i);
    lr = press_button();
    //cout<<lr<<" "<<M<<endl;
    if (lr>M)move_outside(i);
    else in.insert(i);


  }


  for (auto it : in)move_outside(it);

  if (lr < M)return -1;
  return in.size();

}



int min_cardinality(int N) {

  int groups = getnum(N, 1);
  int l = 0;
  int r = N/groups + 1;

  while (l + 1 < r){


    int m = (l + r) /2;
    
    int rta  = getnum(N,m);
//cout<<m<<" | "<<rta<<endl;



    if (rta==groups*m)l = m;
    else r = m;

  }

  if (getnum(N,l)==l*groups)return l;
  else return l+1;
}

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