| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1224171 | Sharky | 디지털 회로 (IOI22_circuit) | C++20 | 0 ms | 0 KiB |
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
void conv(set<int> a, set<int> b) {
vector<int> er;
for (auto& x : a) if (!b.count(x)) move_outside(x);
for (auto& x : b) if (!a.count(x)) move_inside(x);
}
set<int> cur;
vector<int> index;
random_device rd;
mt19937 g(rd());
int min_cardinality(int N) {
set<int> base;
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() == 1) base.insert(i);
else move_outside(i);
index.push_back(i);
}
shuffle(index.begin(), index.end(), g);
vector<bool> bye(N, 0);
int sz = base.size();
cur = base;
int lo = 2, hi = N / sz;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
conv(cur, base);
cur = base;
vector<int> vt;
for (int x = 0; x < N; x++) {
int i = index[x];
if (cur.count(i) || bye[i]) continue;
if (cur.size() == sz * mid) {
vt.push_back(i);
continue;
}
move_inside(i);
if (press_button() <= mid) cur.insert(i);
else {
move_outside(i);
vt.push_back(i);
}
}
if (cur.size() == sz * mid) {
base = cur;
lo = mid;
} else {
for (auto& x : vt) bye[x] = 1;
hi = (cur.size() / sz);
}
}
return 1;
}