Submission #859391

#TimeUsernameProblemLanguageResultExecution timeMemory
859391MasterDobbyRarest Insects (IOI22_insects)C++17
0 / 100
35 ms940 KiB
#include <bits/stdc++.h> #include "insects.h" #define all(a) a.begin(),a.end() #define pii pair<int,int> using namespace std; using ll = long long; int ch[2020]; int min_cardinality(int n){ int cnt=1,mx=0; ch[0]=1; move_inside(0); for(int i=1;i<n;i++){ move_inside(i); int num=press_button(); if(num==1){ ch[i]=1; cnt++; mx=n-i; } else{ move_outside(i); } } if(cnt==1) return n; // for(int i=0;i<n;i++){ // if(ch[i]) continue; // move_inside(i); // } // mx=min(mx,press_button()); // for(int i=0;i<n;i++){ // if(ch[i]) continue; // move_outside(i); // } int l=1,r=min((int)n/cnt+1,mx),now=cnt; while(l<r){ int mid=(l+r+1)/2; int cnt2=now; vector<int> nw; for(int j=0;j<n;j++){ if(cnt2==mid*cnt) break; if(ch[j]) continue; move_inside(j); int num=press_button(); if(num<=mid){ ch[j]=1; nw.push_back(j); cnt2++; mx=min(mx,n-j); } else{ move_outside(j); } } if(cnt2==mid*cnt){ l=mid,now=cnt2; r=mx; } else{ r=mid-1; for(auto x:nw) move_outside(x),ch[x]=0; } } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...