Submission #1203059

#TimeUsernameProblemLanguageResultExecution timeMemory
1203059LucaLucaMRarest Insects (IOI22_insects)C++20
25 / 100
98 ms432 KiB
#include "insects.h" #include <vector> #include <algorithm> #include <cassert> #include <random> #include <iostream> std::mt19937 rng(123); int min_cardinality(int n) { std::vector<int> reprezentant; std::vector<int> order(n); for (int i = 0; i < n; i++) { order[i] = i; } std::shuffle(order.begin(), order.end(), rng); for (int i : order) { move_inside(i); if (press_button() >= 2) { move_outside(i); } else { reprezentant.push_back(i); } } std::vector<bool> taken(n, false); if ((int) reprezentant.size() > n / 2) { return 1; } int mini = n; for (int i : reprezentant) { taken[i] = true; int me = 1; // doar pe i move_inside(i); for (int x : order) { if (me >= mini) { break; } if (!taken[x]) { move_inside(x); if (press_button() == 2) { taken[x] = true; me++; } move_outside(x); } } move_outside(i); mini = std::min(mini, me); } return mini; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...