#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int min_cardinality(int N)
{
int num_insects = 0;
set<int> s;
vector<int> order;
for(int i = 0; i < N; i++)
{
order.push_back(i);
}
shuffle(order.begin(), order.end(), RNG);
for(int i = 0; i < N; i++)
{
// cout << "moving inside[1]: " << i << endl;
move_inside(order[i]);
s.insert(order[i]);
num_insects++;
if(press_button() == 2)
{
// cout << "moving outside[1]: " << i << endl;
move_outside(order[i]);
s.erase(order[i]);
num_insects--;
}
}
// cout << "num_insects = " << num_insects << endl;
int l = 2, r = N / num_insects, ans = 1;
bool flag = true;
set<int> last_iteration;
while(l <= r)
{
int mid = (l + r) / 2;
// cout << "mid = " << mid << endl;
// cout << "s.size() = " << s.size() << endl;
if(!flag)
{
for(auto i: last_iteration)
{
// cout << "i = " << i << endl;
// cout << "moving outside[2]: " << i << endl;
move_outside(i);
s.erase(i);
}
}
last_iteration.clear();
// cout << "hello!" << endl;
int current_insects = s.size();
for(int i = 0; i < N; i++)
{
if(s.count(order[i])) continue;
// cout << "moving inside[3]: " << i << endl;
move_inside(order[i]);
s.insert(order[i]);
last_iteration.insert(order[i]);
current_insects++;
if(press_button() > mid)
{
// cout << "moving outside[3]: " << i << endl;
move_outside(order[i]);
s.erase(order[i]);
last_iteration.erase(order[i]);
current_insects--;
}
if(current_insects == mid * num_insects)
{
break;
}
}
// cout << "current_insects = " << current_insects << endl;
if(current_insects == mid * num_insects)
{
ans = mid;
l = mid + 1;
flag = true;
}
else
{
r = mid - 1;
flag = false;
}
}
return ans;
}
