Submission #1190790

#TimeUsernameProblemLanguageResultExecution timeMemory
1190790LudisseyRarest Insects (IOI22_insects)C++17
100 / 100
15 ms572 KiB
#include "insects.h" #include <bits/stdc++.h> #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; set<int> in; set<int> out; int tps=0; int n; int extr=0; vector<int> re; int press() { return (press_button()+extr); } int countType(vector<int> *to_in){ for (auto u : *to_in) { in.insert(u); move_inside(re[u]); int ans=press(); if(ans>1) { move_outside(re[u]); out.insert(u); in.erase(u); } } return sz(in); } int min_cardinality(int N) { n=N; extr=0; vector<int> al(N); for (int i = 0; i < N; i++) al[i]=i; re=al; random_device rd; mt19937 g(rd()); shuffle(all(re),g); tps=countType(&al); int l=1,r=n/tps; int ans=1; set<int> lst=in; int rm=0; while(l<=r){ int mid=(l+r)/2; queue<int> to_add; for (auto u : out) { move_inside(re[u]); in.insert(u); if(press()>mid) { in.erase(u); move_outside(re[u]); } else to_add.push(u); if(sz(in)==tps*(mid-extr)) break; } while(!to_add.empty()) { int u=to_add.front(); to_add.pop(); out.erase(u); } if(sz(in)==tps*(mid-extr)) { l=mid+1; ans=mid; lst.clear(); lst=in; extr=mid; rm+=sz(in); for (auto u : in) move_outside(re[u]); in.clear(); }else{ r=mid-1; out.clear(); for (auto u : in) { out.insert(u); move_outside(re[u]); to_add.push(u); } while(!to_add.empty()) { int u=to_add.front(); to_add.pop(); in.erase(u); } } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...