Submission #1077362

#TimeUsernameProblemLanguageResultExecution timeMemory
1077362Faisal_SaqibRarest Insects (IOI22_insects)C++17
0 / 100
1 ms344 KiB
#include <bits/stdc++.h> using namespace std; void move_inside(int i); void move_outside(int i); int press_button(); map<set<int>,int> store; set<int> cur,real_; void add(int i) { i--; cur.insert(i); } void rem(int i) { i--; if(cur.find(i)!=cur.end()) cur.erase(i); } void khatam() { cur.clear(); } int ask() { if(store.find(cur)!=store.end())return store[cur]; for(auto i:cur) { if(real_.find(i)==real_.end()) { real_.insert(i); move_inside(i); } } set<int> rem; for(auto j:real_) { if(cur.find(j)==cur.end()) { rem.insert(j); move_outside(j); } } for(auto i:rem)real_.erase(i); return store[cur]=press_button(); } const int M=2e3+10; int par[M],sz[M]; int get(int x) { if(par[x]==x)return x; return par[x]=get(par[x]); } void merge(int x,int y) { x=get(x); y=get(y); par[y]=x; sz[x]+=sz[y]; } int min_cardinality(int n) { for(int i=1;i<=n;i++) par[i]=i,sz[i]=1; vector<int> heads={1}; for(int i=2;i<=n;i++) { int sz=heads.size(); int s=0,e=sz; // can be head[s] // not head[e] while(s+1<e) { int mid=(s+e)/2; khatam(); for(int j=s;j<=mid;j++) add(heads[j]); add(i); int aft=ask(); if(aft==2) { e=mid; } else { s=mid; } } if(e==sz) { heads.push_back(i); } else { merge(heads[e],i); } } int mi=n+1; for(auto i:heads) mi=min(mi,sz[i]); return mi; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...