# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1124216 | epicci23 | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KiB |
#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 2e3 + 5;
int vis[N], D , tot = 0 , kill[N];
inline bool Add(int x){
if(vis[x]) return 0;
vis[x]=1;
tot++;
move_inside(x);
return 1;
}
inline bool Rem(int x){
if(!vis[x]) return 0;
vis[x]=0;
tot--;
move_outside(x);
return 1;
}
inline int Get(){
return press_button();
}
int min_cardinality(int n){
for(int i=0;i<n;i++){
Add(i);
if(i == 0 || Get() == 1) continue;
Rem(i);
}
D = tot;
if(D > n / 2) return 1;
if(D == 1) return n;
int l = 2 , r = n / D , ans = 1;
while(l <= r){
int B = (l + r) / 2;
vector<int> to_kill;
for(int i = 0 ; i < n ; i++){
if(vis[i] || kill[i]) continue;
Add(i);
if(tot > B && Get() > B){
Rem(i);
to_kill.push_back(i);
}
}
if(tot == B * D){
ans = B;
l = B + 1;
}
else{
for(int x : to_kill) kill[x] = 1;
r = tot / D;
}
}
return ans;
}