#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
vector<int> temp;
int d = 0;
for (int i = 0; i < N; i++){
move_inside(i);
int count = press_button();
if (count > 1){
move_outside(i);
}
else{
temp.push_back(i);
d++;
}
}
for (int i = 0; i < temp.size(); i++){
move_outside(temp[i]);
}
int l = 1, r = N / d, mid;
int ans = N;
set<int> all;
for (int i = 0; i < N; i++){
all.insert(i);
}
vector<bool> done(N, 0);
vector<int> take;
vector<int> oldTake;
while(l <= r){
mid = (r - l) / 2 + l;
// cout << mid << " AA\n";
int loop = 0;
auto it = all.begin();
while (it != all.end()){
if (done[*it]){
it = next(it);
continue;
}
move_inside(*it);
done[*it] = 1;
int count = press_button();
loop++;
if (count > mid){
// loop++;
move_outside(*it);
done[*it] = 0;
}
else{
take.push_back(*it);
if (take.size() + oldTake.size() == mid * d) break;
}
it = next(it);
}
if (take.size() + oldTake.size() == mid * d){
ans = mid;
l = mid + 1;
for (auto &num : take){
oldTake.push_back(num);
all.erase(num);
}
take.clear();
}
else{
r = mid - 1;
all.clear();
// cout << take.size() << " SIZEEEEEEE\n";
for (auto &num : take){
done[num] = 0;
move_outside(num);
all.insert(num);
}
take.clear();
}
// cout << "Loop Done: " << loop << "\n";
}
return ans;
return 1;
}
