| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 859351 | 2023-10-10T04:47:11 Z | thinknoexit | 드문 곤충 (IOI22_insects) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
using ll = long long;
int in[2020];
int min_cardinality(int n) {
int type = 0;
for (int i = 0;i < n;i++) {
move_inside(i);
if (press_button() == 2) {
move_outside(i);
}
else in[i] = 1, type++;
}
for (int i = 0;i < n;i++) if (in[i]) move_outside(i);
if (type == 1) return n;
if (type > n / 2) return 1;
int mxans = n / type;
int l = 1, r = mxans;
int sz = type;
while (l < r) {
int mid = (l + r + 1) / 2;
stack<int> s;
for (int i = 0;i < n;i++) {
if (in[i]) continue;
move_inside(i);
if (press_button() > mid) move_outside(i);
else in[i] = 1, s.push(i), sz++;
if (sz == type * mid) break;
}
if (sz < type * mid) {
int S = (l + mid) / 2;
while (!st.empty()) {
move_outside(s.top());
in[s.top()] = 0;
s.pop();
sz--;
if (press_button() <= type * S) break;
}
r = mid - 1;
}
else l = mid;
}
return l;
}