#include "bits/stdc++.h"
#include "insects.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
vector<int> mach;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N;
void clear_mach(){
while(!mach.empty()){
move_outside(mach.back());
mach.pop_back();
}
}
int solve(vector<int> cand){
clear_mach();
if(sz(cand)==1) return 1;
shuffle(all(cand),rng);
int n=sz(cand);
move_inside(cand[0]);
mach.push_back(cand[0]);
int last=1;
for(int i=1;i<n;i++){
move_inside(cand[i]);
mach.push_back(cand[i]);
if(last==press_button()){
move_outside(cand[i]);
mach.pop_back();
}
else last++;
}
int ans=last;
if(last==1) return 1;
vector<int> vis(N,0);
for(int x:mach) vis[x]=1;
clear_mach();
vector<int> cand_new;
for(int x:cand) if(!vis[x]) cand_new.push_back(x);
cand=cand_new;
if(sz(cand)==1) return 1;
shuffle(all(cand),mt19937(0));
vector<int> takla;
for(int x:cand){
move_inside(x);
mach.push_back(x);
int cur = press_button();
if(cur>=last){
move_outside(x);
mach.pop_back();
takla.push_back(x);
}
}
if(takla.empty()){
clear_mach();
return solve(cand);
}
clear_mach();
vector<int> cikar;
for(int x:takla) cikar.push_back(x);
move_inside(takla[0]);
mach.push_back(takla[0]);
for(int i=1;i<sz(takla);i++){
move_inside(takla[i]);
mach.push_back(takla[i]);
if(press_button()==2){
move_outside(takla[i]);
mach.pop_back();
}
}
for(int x:cand){
move_inside(x);
mach.push_back(x);
if(press_button()==2){
move_outside(x);
mach.pop_back();
cikar.push_back(x);
}
}
vis.assign(N,0);
for(int x:cikar) vis[x]=1;
vector<int> newnew;
for(int x:cand) if(!vis[x]) newnew.push_back(x);
cand=newnew;
return min(ans,solve(cand));
}
int min_cardinality(int n){
N=n+5;
vector<int> res;
for(int i=0;i<n;i++) res.push_back(i);
return solve(res);
}
/*void _(){
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
