Submission #629392

#	Time	Username	Problem	Language	Result	Execution time	Memory
629392		kdh9949	Rarest Insects (IOI22_insects)	C++17	99.31 / 100	74 ms	420 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

const int M = 2005;
int chk[M], mst[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;
  if(K == 1) return N;
  for(int i = 0; i < N; i++) mst[i] = chk[i];

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

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