Submission #1078193

#TimeUsernameProblemLanguageResultExecution timeMemory
1078193UmairAhmadMirzaRarest Insects (IOI22_insects)C++17
99.95 / 100
52 ms1368 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); int min_cardinality(int N){ int type=0; set<int> in,out; for(int i=0;i<N;i++){ move_inside(i); in.insert(i); if(press_button()>1){ move_outside(i); in.erase(i); } else type++; } for (int i = 0; i < N; ++i) out.insert(i); for(int i:in) out.erase(i); in.clear(); int low=1,high=(N/type)+1; int bef=type; while(high-low>1){ int mid=(high+low)/2; int cnt=0; for(int i:out){ move_inside(i); in.insert(i); if(press_button()>mid){ move_outside(i); in.erase(i); } else cnt++; if (cnt+bef==type*mid) break; } if(cnt+bef==type*mid){ low=mid; if(high-low<=1) break; bef+=cnt; for(int i:in) out.erase(i); in.clear(); } else{ high=mid; if(high-low<=1) break; out.clear(); for(int i:in){ move_outside(i); out.insert(i); } in.clear(); } } return low; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...