| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162444 | The_Samurai | Rarest Insects (IOI22_insects) | C++20 | 0 ms | 0 KiB |
#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
mt19937 rng(time(0));
int rand(int l, int r) {
int x = rng(); x = abs(x);
return x % (r - l + 1) + l;
}
int min_cardinality(int n) {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
for (int i = 1; i < n; i++) swap(ord[i], ord[rand(0, i)]);
vector<bool> vis(n);
vector<int> pos = {0};
move_inside(0);
for (int i = 1; i < n; i++) {
move_inside(i);
int x = press_button();
if (x > 1) {
move_outside(i);
} else {
pos.emplace_back(i);
}
}
for (int x: pos) vis[x] = true;
int sq = min(n, 2 * sqrt(n));
if (pos.size() <= sq) {
int ans = 1e9;
for (int t = 0; t < pos.size(); t++) {
int old = 1;
vector<int> added;
for (int i: ord) {
if (vis[i]) continue;
move_inside(i);
int nw = press_button();
if (nw == old) {
move_outside(i);
} else {
added.emplace_back(i);
vis[i] = true;
old = nw;
// if (nw >= ans) break;
}
}
for (int x: added) move_outside(x);
ans = min(ans, old);
if (ans == 1) break;
}
return ans;
}
if (pos.size() == 1) return n;
if (pos.size() == n) return 1;
auto ok = [&](int mid) -> bool {
int cnt = count(vis.begin(), vis.end(), true);
vector<int> added;
for (int i: ord) {
if (vis[i]) continue;
move_inside(i);
int now = press_button();
if (now > mid) {
move_outside(i);
} else {
added.emplace_back(i);
cnt++;
}
}
if (cnt == mid * pos.size()) {
for (int x: added) vis[x] = true;
return true;
}
for (int x: added) move_outside(x);
return false;
};
int lx = 2, rx = n / pos.size(), best = 1;
while (lx <= rx) {
int mid = (lx + rx) >> 1;
if (ok(mid)) {
best = mid;
lx = mid + 1;
} else {
rx = mid - 1;
}
}
return best;
}