| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1058202 | epicci23 | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
int N;
void clear_mach(){
while(!mach.empty()){
move_outside(mach.back());
mach.pop_back();
}
}
int solve(vector<int> cand){
if(sz(cand)==1) return 1;
random_shuffle(all(cand),mt19937(0));
int n=sz(cand);
clear_mach();
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;
random_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 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;
}*/