#include "insects.h" #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> #include <array> using namespace std; #ifdef LOCAL #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);} #else #define eprintf(...) 42 #endif using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; template<typename T> using pair2 = pair<T, T>; using pii = pair<int, int>; using pli = pair<ll, int>; using pll = pair<ll, ll>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second clock_t startTime; double getCurrentTime() { return (double)(clock() - startTime) / CLOCKS_PER_SEC; } const int N = 2023; int n; int d; int c; bool used[N]; void findDistinct() { vector<int> p; for (int i = 0; i < n; i++) { move_inside(i); if (press_button() == 1) p.push_back(i); else move_outside(i); } for (int i : p) used[i] = true; d = (int) p.size(); } bool check(int x) { c = 0; for (int i = 0; i < n; i++) c += used[i]; vector<int> ids; for (int i = 0; i < n; i++) if (!used[i]) ids.push_back(i); shuffle(all(ids), rng); vector<int> p; for (int i : ids) { move_inside(i); if (press_button() > x) move_outside(i); else c++, p.push_back(i); if (c == x * d) break; } if (c == x * d) { for (int i : p) used[i] = true; return true; } else { for (int i : p) move_outside(i); return false; } } int min_cardinality(int N) { n = N; findDistinct(); if (d == 1) return N; if (d == 2) { for (int i = 0; i < N; i++) if (!used[i]) move_inside(i); return n - press_button(); } int l = 1, r = n / d + 1; while(r - l > 1) { int mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid, r = min(r, c / d + 1); } return l; }