#include "insects.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int NN = 1e5 + 10;
bool in[NN];
mt19937 rng(10184104810471);
ll rnd(ll l, ll r) {
return l + rng() % (r - l + 1);
}
ll min_cardinality(ll n) {
ll type = 0;
vector<ll> candidate;
for(ll i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 1) {
++type;
in[i] = 1;
}
else {
move_outside(i);
candidate.push_back(i);
}
}
ll l = 2, r = n / type, ans = 1;
ll cur = 1;
while (l <= r) {
shuffle(candidate.begin(), candidate.end(), rng);
ll mid = (l + r + 1) / 2;
assert(cur <= mid);
ll last = cur;
for(auto &i : candidate) {
move_inside(i);
ll nxt = press_button();
if (nxt > mid) {
move_outside(i);
in[i] = 0;
}
else {
cur = nxt;
in[i] = 1;
}
}
ll total = 0;
for(ll i = 0; i < n; i++) total += in[i];
vector<ll> _candidate;
if (cur == mid && mid * type == total) {
for(auto &i : candidate) if (!in[i]) _candidate.push_back(i);
l = mid + 1;
ans = mid;
}
else {
for(auto &i : candidate) if (in[i]) {
_candidate.push_back(i);
move_outside(i);
in[i] = 0;
}
r = mid - 1;
cur = last;
}
candidate = _candidate;
}
return ans;
}
Compilation message
/usr/bin/ld: /tmp/ccahYMHt.o: in function `main':
stub.cpp:(.text.startup+0x61): undefined reference to `min_cardinality(int)'
collect2: error: ld returned 1 exit status
