#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N)
{
vector<int> type(N, 0);
for (int i = 0; i < N; i++)
type[i] = i;
int num = 1;
swap(type[0], type.back());
type.pop_back();
move_inside(0);
random_shuffle(type.begin(), type.end());
for (int i = 0; i < type.size(); i++)
{
move_inside(type[i]);
int temp = press_button();
if (temp == 1)
{
swap(type[i], type.back());
type.pop_back();
i--;
num++;
}
else
move_outside(type[i]);
}
if (num == 1)
return N;
int left = N - num, cur = 1;
while (left)
{
int targ = max(cur + 1, cur + (int)round((double)left / (double)(2 * num)));
if (left < num)
return cur;
vector<int> news, outs;
for (int i = 0; i < type.size(); i++)
{
move_inside(type[i]);
int temp = press_button();
if (temp > targ)
{
outs.push_back(type[i]);
move_outside(type[i]);
}
else
{
news.push_back(type[i]);
}
}
if (news.size() == (targ - cur) * num)
{
type = outs;
left -= news.size();
cur = targ;
}
else
{
type = news;
left -= outs.size();
for (auto v : news)
move_outside(v);
}
}
return cur;
}
