void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N);
#include <iostream>
#include <vector>
#include <set>
bool markMax[2010];
bool markMin[2010];
int type[2010];
std::set<int> clearList;
int ct = 1;
int markcnt = 0;
int recentmin = 2000;
int recentmax = 2000;
int size;
int pbv = 0;
int clear(){
for(auto c:clearList){
move_outside(c);
}
return 0;
}
int maxL(){
//this cost atmost 2*N,2*N,2*N including clear
//assuming empty
//return the max cardinallity as well as marking them
int count=1;
int last = 0;
int nw = -1;
for(int i=0;i<size;i++){
if(markMax[i]||markMin[i])continue;
move_inside(i);
pbv = press_button();
if(pbv>last){
nw = i;
}
last = pbv;
}
if(nw==-1)return 0;
type[nw]=ct++;
markMax[nw]=true;
last = pbv;
for(int i=0;i<size;i++){
if(markMax[i]||markMin[i])continue;
move_outside(i);
pbv = press_button();
if(pbv<last){
markMax[i]=true;
count+=1;
type[i]=type[nw];
move_inside(i);
clearList.insert(i);
}
}
clear();
return count;
}
int minL(){
//this cost atmost N,N,N including clear
//assuming empty
//return amount of type of insect as well as marking non-duplicate
int count = 0;
for(int i=0;i<size;i++){
if(markMax[i]||markMin[i])continue;
move_inside(i);
pbv = press_button();
if(pbv>1){
move_outside(i);
}
else{
count+=1;
markMin[i]=true;
clearList.insert(i);
}
}
clear();
return count;
}
int min_cardinality(int N) {
size=N;
int lastC=0;
int lastG=0;
int q=0;
int mlc = 0;
while(q++<10000){
int gs1 = maxL();if(gs1!=0)lastC-=1;
int ds1 = minL();mlc+=1;
for(int i=0;i<N;i++){
std::cout << '(' << markMax[i] << ',' << markMin[i] << ')';
}
std::cout << gs1 << ' ' << ds1 << '\n';
if(gs1==1){
return mlc;
}
if(lastC>ds1&&lastC!=-1){
return mlc-1;
}
lastC=ds1;
lastG=gs1;
}
return 0;
}
