제출 #1356279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356279		hexopia	드문 곤충 (IOI22_insects)	C++20	99.89 / 100	11 ms	436 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int n,num;
int min_cardinality(int N) {
  n = num = N;
  vector<int> a;
  vector<bool> mark(n,0);
  for(int i = 0 ; i<n; ++i) {
    move_inside(i);
    if(press_button() > 1) move_outside(i),mark[i] = 1,num--;
  }
  for(int i = 0 ; i<n ;++i) if(mark[i]) a.push_back(i);
  int l = 1,r = n/num;
  while(l<r) {
    int md = (l+r+1)/2;
    int cnt = l*num;
    vector<int> a1,a2;
    for(int x:a) {
      move_inside(x);
      if(press_button() > md) move_outside(x),a2.push_back(x);
      else a1.push_back(x),cnt++;
    }
    if(cnt == md*num) {
      a = a2;
      l = md;
    }
    else {
      for(int x:a1) move_outside(x);
      a = a1;
      r = md-1;
    }
  }
  return l;
}

• 서브태스크 1: 10 / 10
• 서브태스크 2: 15 / 15
• 서브태스크 3: 74.89 / 75