Submission #1074621

#TimeUsernameProblemLanguageResultExecution timeMemory
1074621NicolaikrobRarest Insects (IOI22_insects)C++17
99.89 / 100
49 ms956 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; typedef vector<int> vi; int n, tc, il, rc = 0; set<int> M, IU; vi IS; void mi(int i) { move_inside(IS[i]); M.insert(i); } void mo(int i) { move_outside(IS[i]); M.erase(i); } int pb() { return press_button()+rc; } void rm(bool t) { if(t) { for(auto x : M) { IU.erase(x); move_outside(IS[x]); } il -= M.size(); rc += M.size()/tc; M.clear(); } else { IU = M; il = M.size(); for(auto x : M) move_outside(IS[x]); M.clear(); } } bool tjek(int g) { for(auto i : IU) { mi(i); if(pb() > g) mo(i); } bool s = (int(M.size())+rc*tc == tc*g); rm(s); return s; } int min_cardinality(int N) { il = n = N; IS.resize(n); for(int i = 0; i < n; i++) IS[i] = i; srand(time(NULL)); random_shuffle(IS.begin(), IS.end()); mi(0); for(int i = 1; i < n; i++) { mi(i); if(pb() > 1) mo(i); } tc = M.size(); for(int i = 0; i < n; i++) IU.insert(i); rm(1); int l = 1, u = n/tc; while(l < u) { int g = (l+u+1)/2; if(tjek(g)) l = g; else u = g-1; } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...