#include "insects.h"
#include <vector>
#include <iostream>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int mx = 2'000;
vi ins(mx, 0);
int ct = 0;
void move_in(int i)
{
// cerr << "insert " << i << '\n';
if(ins[i])
return;
ins[i] = 1;
move_inside(i);
ct++;
}
void move_out(int i)
{
// cerr << "erase " << i << '\n';
if(!ins[i])
return;
ins[i] = 0;
move_outside(i);
ct--;
}
int min_cardinality(int N)
{
int types = 0;
vi is_basic(N, 0);
for(int i = 0; i < N; i++)
{
move_in(i);
if(press_button() >= 2)
move_out(i);
else
{
is_basic[i] = 1;
types++;
}
}
for(int i = 0; i < N; i++)
move_out(i);
int lg = 0;
while((1<<lg) < N/types)
lg++;
vi cand;
for(int i = 0; i < N; i++)
cand.push_back(i);
int tst = 0;
for(int b = lg-1; b >= 0; b--)
{
int ntst = tst + (1<<b);
vi inserted;
vi not_inserted;
for(int i : cand)
{
if(ntst * types == ct)
{
not_inserted.push_back(i);
continue;
}
move_in(i);
if(press_button() > ntst)
{
move_out(i);
not_inserted.push_back(i);
}
else
inserted.push_back(i);
}
if(ct == types * ntst)
{
tst = ntst;
cand = not_inserted;
inserted.clear();
not_inserted.clear();
}
else
{
for(int i : inserted)
move_out(i);
cand = inserted;
inserted.clear();
not_inserted.clear();
}
}
return tst;
}
