Submission #1124345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124345		epicci23	Rarest Insects (IOI22_insects)	C++17	100 / 100	87 ms	15952 KiB

insects

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

const int N = 2e3 + 5;

map<vector<int>,int> Cache;
int vis[N], Kill[N] , D , tot = 0;

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

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

inline int Get(){
  vector<int> v;
  for(int i=0;i<N;i++) if(vis[i]) v.push_back(i);
  if(Cache.count(v)) return Cache[v];
  return Cache[v] = press_button();
}

int min_cardinality(int n){
  random_device rd;
  mt19937 rng(rd());
  vector<int> go(n,0);
  iota(go.begin(),go.end(),0);
  shuffle(go.begin(),go.end(),rng);

  for(int i=0;i<n;i++){
    Add(go[i]);
    if(i == 0 || Get() == 1) continue;
    Rem(go[i]);
  }
  for(int i=0;i<n;i++) if(vis[go[i]]) Kill[go[i]] = 1;
  D = tot;
  if(D > n / 2) return 1;
  if(D == 1) return n;
  
  int ans = 1, l = 2 , r = n / D;
  while(l <= r){
    shuffle(go.begin(),go.end(),rng);
    int B = (l + r) / 2;
    for(int i=0;i<n;i++) if(!Kill[go[i]]) Rem(go[i]);
    vector<int> to_kill;
    for(int i = 0 ; i < n ; i++){
      if(vis[go[i]] || Kill[go[i]]) continue;
      if(tot == B * D){
        to_kill.push_back(go[i]);
        continue;
      }
      Add(go[i]);
      if(tot > B && Get() > B){
       Rem(go[i]);
       to_kill.push_back(go[i]);
      }
    }
    if(tot == B * D){
      l = B + 1;
      ans = B;
      r = min(r, B + (int) to_kill.size() / D);
      if(to_kill.size() < D) return ans;
      for(int i=0;i<n;i++) if(vis[go[i]]) Kill[go[i]] = 1;
    }
    else{
      for(int x : to_kill) Kill[x] = 1;
      r = min(tot / D, B - 1);
    }
  }

  return ans;
}

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