#include <bits/stdc++.h>
#include "insects.h"
#define pii pair<int, int>
using namespace std;
set<pii> inside;
set<pii> outside; //Random key, insect index
int types = -1;
int countTypes()
{
while(inside.size() && press_button() > 1)
{
move_outside((*inside.begin()).second);
outside.insert(*inside.begin());
inside.erase(inside.begin());
}
vector<pii> a(0);
for(pii i : outside)
{
a.push_back(i);
}
for(pii i : a)
{
move_inside(i.second);
inside.insert(i);
outside.erase(i);
if(inside.size() > 1)
{
if(press_button() > 1)
{
move_outside(i.second);
outside.insert(i);
inside.erase(i);
}
}
}
return inside.size();
}
bool test(int k) //Every type at least k insects?
{
while(press_button() > k)
{
move_outside((*inside.begin()).second);
outside.insert(*inside.begin());
inside.erase(inside.begin());
}
vector<pii> a(0);
for(pii i : outside)
{
a.push_back(i);
}
for(pii i : a)
{
move_inside(i.second);
inside.insert(i);
outside.erase(i);
if((int) inside.size() > k)
{
if(press_button() > k)
{
move_outside(i.second);
outside.insert(i);
inside.erase(i);
}
}
}
return((int) inside.size() == k*types);
}
int min_cardinality(int N)
{
srand(42);
for(int i = 0; i < N; i++)
{
outside.insert({rand()%100000, i});
}
types = countTypes();
if(types <= 5)
{
while(inside.size())
{
move_outside((*inside.begin()).second);
outside.insert(*inside.begin());
inside.erase(inside.begin());
}
vector<int> a(N);
int counter = 0;
for(pii p : outside)
{
a[counter] = p.second;
counter++;
}
vector<int> card(N, -1);
for(int i = 0; i < N; i++)
{
if(card[a[i]] == -1)
{
move_inside(a[i]);
vector<int> machine = {a[i]};
for(int j = i+1; j < N; j++)
{
if(card[a[j]] == -1)
{
move_inside(a[j]);
machine.push_back(a[j]);
int state = press_button();
if(state != (int) machine.size())
{
move_outside(a[j]);
machine.pop_back();
}
}
}
for(int j : machine)
{
card[j] = machine.size();
move_outside(j);
}
}
}
return *min_element(card.begin(), card.end());
}
int left = 1;
int right = N/types;
while(left < right)
{
int mid = (left+right+1)/2;
if(right-left > 5)
{
mid = left + (right-left)/5;
}
if(test(mid))
{
left = mid;
}
else
{
right = mid-1;
}
}
return left;
}
