/* https://ioi2022.id/data/editorial.pdf */ #include "insects.h" const int N = 2000; 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; for (int i = 0; i < n; i++) if (type[i] == 0) { move_inside(i), type[i] = -1, k++; if (press_button() > c) move_outside(i), type[i] = 0, k--; } if (k == c * d) { lower = c; for (int i = 0; i < n; i++) if (type[i] == -1) type[i] = 1; } else { upper = c; for (int i = 0; i < n; i++) if (type[i] == -1) type[i] = 0; else if (type[i] == 0) type[i] = -2; } } return lower; }