Submission #1266562

#TimeUsernameProblemLanguageResultExecution timeMemory
1266562scalifrastico_098Rarest Insects (IOI22_insects)C++20
53.16 / 100
49 ms416 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; int m, op=0, c=0, pk=0; vector<bool> fg; vector<int> uh; bool f1(int n) { if(uh.empty()) return (c==op*m); vector<int> ind; vector<bool> ag(fg.size()); int i=pk, lk=0, s=uh.size(); while(lk<s&&c<op*m) { move_inside(uh[i]); if(press_button()<=m){fg[uh[i]]=true; c++; ind.push_back(uh[i]); ag[uh[i]]=true;} else move_outside(uh[i]); i++; if(i==s) i=0; lk++; } if(c==op*m) { if(!ind.empty()){uh.erase(remove_if(uh.begin(), uh.end(), [&](int x){ return ag[x]; }), uh.end());} if(uh.empty()) pk=0; else pk=i%uh.size(); return true; } for(auto x:ind){move_outside(x); fg[x]=false; c--;} if(uh.empty()) pk=0; else pk=i%uh.size(); return false; } int min_cardinality(int n) { op=0; c=0; pk=0; fg.assign(n, false); for(int i=0; i<n; i++){move_inside(i); if(press_button()>1) move_outside(i); else {fg[i]=true; c++; op++;}} for(int i=0; i<n; i++) {if(!fg[i]) uh.push_back(i);} if(op<=1) return n; if(op==n) return 1; int l=1, r=n/op; ; while(l<r) { m=(l+r+1)/2;if(f1(n)){l=m;} else r=m-1; } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...