Submission #627792

#TimeUsernameProblemLanguageResultExecution timeMemory
627792peti1234Rarest Insects (IOI22_insects)C++17
99.89 / 100
70 ms328 KiB
#include <bits/stdc++.h> using namespace std; #include "insects.h" const int c=2005; int cnt, si; bool v[c], fix[c]; int add(int a) { assert(!v[a]); v[a]=true; si++; move_inside(a); return press_button(); } void sub(int a) { assert(v[a]); v[a]=false; si--; move_outside(a); } int min_cardinality(int N) { for (int i=0; i<N; i++) { if (add(i)==2) { sub(i); } else { cnt++; } } for (int i=0; i<N; i++) { if (v[i]) { fix[i]=1; } } int lo=1, hi=N/cnt+1, mid; while (hi-lo>1) { mid=(hi+lo)/2; for (int i=0; i<N; i++) { if (fix[i]) continue; if (add(i)>mid) { sub(i); } } if (si==cnt*mid) { lo=mid; for (int i=0; i<N; i++) { if (v[i]) { fix[i]=1; } } } else { hi=mid; for (int i=0; i<N; i++) { if (fix[i]) continue; if (!v[i]) fix[i]=1; else { sub(i); } } } } return lo; } /* int main() { return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...