# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1233078 | adriines06 | 드문 곤충 (IOI22_insects) | C++20 | 0 ms | 0 KiB |
#include "const.h"
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
set<int>u;
for(int i=0;i<N;i++){
move_inside(i);
int m= press_button();
if(m==1){
u.insert(i);
}
else{
move_outside(i);
}
}
if((int)u.size()==N) return 1;
int M=u.size();
int ans=5000;
//cout<<M<<"\n";
vector<int>v(u.size());
for(int i=0;i<M;i++){
int ind=*u.begin();
v[i]=ind;
u.erase(u.begin());
move_outside(i);
}
for(int i=0;i<M;i++){
int cont=1;
int ind=v[i];
move_inside(ind);
u.insert(i);
for(int j=ind+1;j<N;j++){
if(u.count(j)==0){
move_inside(j);
int m= press_button();
if(m>1){
//cout<<j<<" ";
cont++;
u.insert(j);
}
else{
move_outside(j);
}
}
u.erase(u.begin());
}
ans=min(cont,ans);
}
return ans;
}