| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 893137 | 2023-12-26T14:50:53 Z | Trisanu_Das | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KB |
#include"insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int k, diff = 0;
set<int> in;
for(int i = 0; i < N; ++i) {
in.insert(i);
move_inside(i);
k = press_button();
if(k == 2) {
in.erase(i);
move_outside(i);
continue;
}
diff++
}
int l = 1, r = N / diff;
vector<bool> skp(N);
while(l < r) {
int mid = (l + r + 1) / 2;
vector<int> lst_added, ws;
for(int i = 0; i < N; ++i) {
if(skp[i] || !in.insert(i).second) continue;
move_inside(i);
k = press_button();
if(k > mid) {
in.erase(i);
move_outside(i);
ws.push_back(i);
continue;
}
lst_added.push_back(i);
if(diff * mid == (int)in.size()) break;
}
if((int)in.size() < diff * mid) {
r = mid - 1;
if(l == r) continue;
for(auto& u : lst_added) {
in.erase(u);
move_outside(u);
}
for(auto& u : ws) skp[u] = 1;
} else l = mid;
}
return (l + r) / 2;
}