제출 #629249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629249		kdh9949	드문 곤충 (IOI22_insects)	C++17	83.67 / 100	107 ms	400 KiB

insects

#include "insects.h"

const int M = 2005;
int chk[M], exc[M], cnt;

int IN(int x) {
  if(chk[x]) return 0; 
  chk[x] = 1;
  cnt++;
  move_inside(x);
  return 1;
}

int OUT(int x) {
  if(!chk[x]) return 0;
  chk[x] = 0;
  cnt--;
  move_outside(x);
  return 1;
}

int GET() { return press_button(); }

int min_cardinality(int N) {
  IN(0);
  for(int i = 1; i < N; i++) {
    IN(i);
    if(GET() != 1) OUT(i);
  }
  int K = cnt;

  int L = 1, R = N / K;
  while(L < R) {
    int M = (L + R) / 2;
    for(int i = 0; i < N; i++) if(!exc[i]) {
      if(IN(i)) {
        if(GET() > M + 1) OUT(i);
      }
    }
    if(cnt == (M + 1) * K) L = M + 1;
    else {
      for(int i = 0; i < N; i++) if(!OUT(i)) exc[i] = 1;
      R = M;
    }
  }
  return L;
}

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