Submission #826335

#TimeUsernameProblemLanguageResultExecution timeMemory
826335alvingogoRarest Insects (IOI22_insects)C++17
99.91 / 100
55 ms336 KiB
#include "insects.h" #include <bits/stdc++.h> #define fs first #define sc second using namespace std; struct DSU{ vector<int> bo; void init(int x){ bo.resize(x); iota(bo.begin(),bo.end(),0); } int find(int x){ return bo[x]==x?bo[x]:bo[x]=find(bo[x]); } void merge(int x,int y){ x=find(x); y=find(y); bo[x]=y; } }dsu; int min_cardinality(int n) { int cnt=0; dsu.init(n); vector<int> vis(n); vector<int> bo(n); for(int i=0;i<n;i++){ move_inside(i); int a=press_button(); if(a>1){ move_outside(i); } else{ vis[i]=1; cnt++; } } if(cnt==1){ return n; } if(cnt<=3){ vector<int> cg; for(int w=0;w<cnt;w++){ int k=1; vector<int> vz(n); for(int i=0;i<n;i++){ if(!vis[i]){ move_inside(i); int a=press_button(); if(a==k){ move_outside(i); } else{ vz[i]=1; k=a; } } } for(int i=0;i<n;i++){ if(vz[i]){ vis[i]=1; move_outside(i); } } cg.push_back(k); } return *min_element(cg.begin(),cg.end()); } else{ int l=1,r=(n-1)/cnt+2; int cc=cnt; while(r>l){ int m=(l+r)/2; vector<int> pu(n); for(int i=0;i<n;i++){ if(!vis[i]){ move_inside(i); cc++; int a=press_button(); if(a>m){ move_outside(i); cc--; } else{ pu[i]=1; } } } if(m*cnt!=cc){ r=m; for(int i=0;i<n;i++){ if(pu[i]){ move_outside(i); cc--; } else{ vis[i]=1; } } } else{ l=m+1; for(int i=0;i<n;i++){ if(pu[i]){ vis[i]=1; } } } } return l-1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...