Submission #1185418

#TimeUsernameProblemLanguageResultExecution timeMemory
1185418anmattroiRarest Insects (IOI22_insects)C++17
25 / 100
71 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 polySolution(int N) { for (int i = 0; i < N; i++) moveInside(i); vector<int> inside, outside; inside.resize(N); iota(inside.begin(), inside.end(), 0); while (1) { int X = pressButton(); if (X == 1 || X == inside.size()) return X; for (int i : inside) { moveOutside(i); int T = pressButton(); if (T == X) { moveOutside(i); outside.emplace_back(i); } else moveInside(i); } for (int i : inside) if (!binary_search(outside.begin(), outside.end(), i)) moveOutside(i); for (int i : outside) moveInside(i); swap(outside, inside); outside.clear(); } } 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/6) { return polySolution(N); } 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...