/* https://ioi2022.id/data/editorial.pdf */
#include "insects.h"
const int N = 2000;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ii[N]; char type[N];
int min_cardinality(int n) {
int d = 0;
for (int i = 0; i < n; i++) {
move_inside(i), type[i] = 1, d++;
if (press_button() > 1)
move_outside(i), type[i] = 0, d--;
}
int lower = 1, upper = n / d + 1, k = d;
while (upper - lower > 1) {
int c = (lower + upper) / 2, m = 0;
for (int i = 0; i < n; i++)
if (type[i] == 0)
ii[m++] = i;
for (int h = 0; h < m; h++) {
int h_ = rand_() % (h + 1), tmp;
tmp = ii[h], ii[h] = ii[h_], ii[h_] = tmp;
}
for (int h = 0; h < m; h++) {
int i = ii[h];
move_inside(i), type[i] = -1, k++;
if (press_button() > c)
move_outside(i), type[i] = 0, k--;
else if (k == c * d)
break;
}
if (k == c * d) {
lower = c;
for (int i = 0; i < n; i++)
if (type[i] == -1)
type[i] = 1;
} else {
upper = k / d + 1;
for (int i = 0; i < n; i++)
if (type[i] == -1)
move_outside(i), type[i] = 0, k--;
else if (type[i] == 0)
type[i] = -2;
}
}
return lower;
}
