Submission #1185415

#TimeUsernameProblemLanguageResultExecution timeMemory
1185415anmattroiRarest Insects (IOI22_insects)C++17
25 / 100
69 ms452 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<int> p; int pressButton() { return press_button(); } void moveInside(int i) { move_inside(p[i]); } void moveOutside(int i) { move_outside(p[i]); } int ok(int N, int X) { vector<int> A, B; for (int i = 0; i < N; i++) { moveInside(i); int T = pressButton(); if (T >= X) { moveOutside(i); B.emplace_back(i); } } for (int i : B) { moveInside(i); int T = pressButton(); if (T > X) { moveOutside(i); A.emplace_back(i); } } int diff = int(B.size()) - int(A.size()); return diff * X < N - int(A.size()); } int min_cardinality(int N) { p.assign(N, 0); iota(p.begin(), p.end(), 0); shuffle(p.begin(), p.end(), rng); int lo = 1, hi = N+1; while (hi - lo > 1) { int mid = (lo + hi) >> 1; if (ok(N, mid)) hi = mid; else lo = mid; if (lo >= N/2) { for (int i = 0; i < N; i++) moveInside(i); int T = pressButton(), Z = N-T; if (Z == 0) Z = INT_MAX; return min(T, Z); } if (lo != hi) for (int i = 0; i < N; i++) moveOutside(i); } return lo; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...