Submission #698948

#TimeUsernameProblemLanguageResultExecution timeMemory
698948aryan12Rarest Insects (IOI22_insects)C++17
53.16 / 100
165 ms580 KiB
#include "insects.h" #include <bits/stdc++.h> using namespace std; int min_cardinality(int N) { int num_insects = 0; set<int> s; for(int i = 0; i < N; i++) { // cout << "moving inside[1]: " << i << endl; move_inside(i); s.insert(i); num_insects++; if(press_button() == 2) { // cout << "moving outside[1]: " << i << endl; move_outside(i); s.erase(i); num_insects--; } } // cout << "num_insects = " << num_insects << endl; int l = 2, r = N / num_insects, ans = 1; bool flag = true; set<int> last_iteration; while(l <= r) { int mid = (l + r) / 2; // cout << "mid = " << mid << endl; // cout << "s.size() = " << s.size() << endl; if(!flag) { for(auto i: last_iteration) { // cout << "i = " << i << endl; // cout << "moving outside[2]: " << i << endl; move_outside(i); s.erase(i); } } last_iteration.clear(); // cout << "hello!" << endl; int current_insects = s.size(); for(int i = 0; i < N; i++) { if(s.count(i)) continue; // cout << "moving inside[3]: " << i << endl; move_inside(i); s.insert(i); last_iteration.insert(i); current_insects++; if(press_button() > mid) { // cout << "moving outside[3]: " << i << endl; move_outside(i); s.erase(i); last_iteration.erase(i); current_insects--; } if(current_insects == mid * num_insects) { break; } } // cout << "current_insects = " << current_insects << endl; if(current_insects == mid * num_insects) { ans = mid; l = mid + 1; flag = true; } else { r = mid - 1; flag = false; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...