Submission #1190300

#TimeUsernameProblemLanguageResultExecution timeMemory
1190300LudisseyRarest Insects (IOI22_insects)C++17
25 / 100
2015 ms242576 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; map<set<int>,int> mp; set<int> in; set<int> out; int tps=0; int n; int press(){ if(mp.find(in)==mp.end()) return (mp[in]=press_button()); return mp[in]; } 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; tps=countType(al); int l=1,r=n/tps; int ans=1; 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); } vector<int> tocheck; for (auto u : out) { tocheck.push_back(u); } for (auto u : in) { move_outside(u); out.insert(u); } in.clear(); int ct=countType(tocheck); if(ct==tps) { l=mid+1; }else{ r=mid-1; ans=mid; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...