Submission #634622

#TimeUsernameProblemLanguageResultExecution timeMemory
634622JeanBombeurRarest Insects (IOI22_insects)C++17
100 / 100
63 ms428 KiB
#include "insects.h" #include <iostream> #include <vector> using namespace std; // <|°_°|> // JeanBombeur & M. Broccoli // The hardest choices require the strongest wills // What is better - to be born good, or to overcome your evil nature with great effort ? const int MAX_INSECTS = (2000); vector <int> Alive; vector <int> In; vector <int> Out; int nbTypes = 0; int nbInsects; int Check() { int sz = Alive.size(); int value = (sz + 2 * nbTypes - 1) / (2 * nbTypes); In.clear(); Out.clear(); for (int a : Alive) { move_inside(a); if (press_button() > value) move_outside(a), Out.push_back(a); else In.push_back(a); } for (int a : In) move_outside(a); if ((int)In.size() == value * nbTypes) { Alive = Out; return value; } Alive = In; return 0; } int min_cardinality(int N) { nbInsects = N; int ans = 1; for (int i = 0; i < nbInsects; i ++) { move_inside(i); if (press_button() > 1) move_outside(i), Alive.push_back(i); else nbTypes ++, In.push_back(i); } for (int a : In) move_outside(a); while ((int)Alive.size() >= nbTypes) ans += Check(); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...