Submission #1124207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124207		epicci23	Rarest Insects (IOI22_insects)	C++17	50 / 100	83 ms	424 KiB

insects

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

const int N = 2e3 + 5;

int vis[N],D,tot=0;

inline bool Add(int x){
  if(vis[x]) return 0;
  vis[x]=1;
  tot++;
  move_inside(x);
  return 1;
}

inline bool Rem(int x){
  if(!vis[x]) return 0;
  vis[x]=0;
  tot--;
  move_outside(x);
  return 1;
}

inline int Get(){
  return press_button();
}

int min_cardinality(int n){
  for(int i=0;i<n;i++){
    Add(i);
    if(Get() == 1) continue;
    Rem(i);
  }

  D = tot;
  if(D > n / 2) return 1;
  if(D == 1) return n;
  for(int i = 0; i < n; i++) Rem(i);

  int l = 1 , r = n / D;
  while(l < r){
    int B = (l + r + 1) / 2;
    vector<int> L;
    for(int i = 0 ; i < n ; i++){
      if(Add(i)) L.push_back(i);
      if(Get() > B) L.pop_back() , Rem(i);
    }
    if(tot == B * D) l = B;
    else{
      for(int x : L) Rem(x);
      r = B - 1;
    }
  }

  return l;
}

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