# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1192285 | Luvidi | Rarest Insects (IOI22_insects) | C++20 | 0 ms | 0 KiB |
#include "nuts.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
int c=0;
set<int> s,ls;
for(int i=0;i<n;i++){
move_inside(i);
if(press_button()>1){
move_outside(i);
}else s.insert(i);
}
ls=s;
set<int> sk;
c=s.size();
int l=1,r=n/c;
while(l<r){
int m=l+1+(r-l-1)/2;
set<int> t;
for(int i=0;i<n;i++)if(!s.count(i)&&!sk.count(i)){
move_inside(i);
if(press_button()>m){
move_outside(i);
t.insert(i);
}else s.insert(i);
}
if(s.size()/m==c){
l=m;
ls=s;
}else{
r=m-1;
for(int i=0;i<n;i++){
if(s.count(i)&&!ls.count(i)){
move_outside(i);
s.erase(i);
}else if(!s.count(i)&&ls.count(i)){
move_inside(i);
s.insert(i);
}
}
for(int i:t)sk.insert(i);
}
}
return l;
}