제출 #629981

#제출 시각아이디문제언어결과실행 시간메모리
629981handlename드문 곤충 (IOI22_insects)C++17
99.31 / 100
65 ms1440 KiB
#include <bits/stdc++.h> #include "insects.h" using namespace std; #define pb push_back #define mp make_pair set<int> s; set<int> lol[2001]; void add(int i){ move_inside(i); s.insert(i); } void rem(int i){ move_outside(i); s.erase(i); } int min_cardinality(int n){ for (int i=0;i<n;i++){ add(i); if (press_button()>1){ rem(i); } lol[n].insert(i); } int mini=1,maxi=n/s.size()+1,sz=s.size(); while (mini+1<maxi){ int mid=(mini+maxi)/2-(maxi-mini>5); set<int> added; int id=mid; for (int i=mid;i<=n;i++){ if (!lol[i].empty()){ id=i; break; } } for (auto i:lol[id]){ if (s.find(i)!=s.end()) continue; add(i); if (press_button()>mid) rem(i); else added.insert(i); } lol[mid]=s; if ((int)s.size()==sz*mid){ mini=mid; } else { maxi=mid; for (auto i:added) rem(i); } } return mini; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...