Submission #629272

#	Time	Username	Problem	Language	Result	Execution time	Memory
629272		kdh9949	Rarest Insects (IOI22_insects)	C++17	99.79 / 100	64 ms	552 KiB

insects

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

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

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

int OUT(int x) { x = P[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) {
  mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
  iota(P, P + N, 0);
  shuffle(P, P + N, mt);
  
  IN(0);
  for(int i = 1; i < N; i++) {
    IN(i);
    if(GET() != 1) OUT(i);
  }
  int K = cnt;
  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;
    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[P[i]]) if(!OUT(i)) exc[i] = 1;
      R = M;
    }
  }
  return L;
}

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