Submission #1190776

#TimeUsernameProblemLanguageResultExecution timeMemory
1190776Ludissey드문 곤충 (IOI22_insects)C++17
50.03 / 100
55 ms612 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; vector<int> re; int press() { return press_button(); } int countType(vector<int> *to_in){ for (auto u : *to_in) { in.insert(u); move_inside(u); int ans=press(); if(ans>1) { move_outside(u); out.insert(u); in.erase(u); } } return sz(in); } int min_cardinality(int N) { n=N; vector<int> al(N); for (int i = 0; i < N; i++) al[i]=i; re=al; random_device rd; mt19937 g(rd()); tps=countType(&al); int l=1,r=n/tps; int ans=1; set<int> lst=in; while(l<=r){ int mid=(l+r)/2; queue<int> to_add; for (auto u : out) { move_inside(u); in.insert(u); if(press()>mid) { in.erase(u); move_outside(u); } else to_add.push(u); } while(!to_add.empty()) { int u=to_add.front(); to_add.pop(); out.erase(u); } if(sz(in)==tps*mid) { l=mid+1; ans=mid; lst.clear(); lst=in; }else{ r=mid-1; for (auto u : in) { if(lst.find(u)==lst.end()) { out.insert(u); move_outside(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...