Submission #938943

#TimeUsernameProblemLanguageResultExecution timeMemory
938943irmuunRarest Insects (IOI22_insects)C++17
57.14 / 100
93 ms1712 KiB
#include<bits/stdc++.h> #include "insects.h" using namespace std; #define ll long long #define pb push_back #define ff first #define ss second #define all(s) s.begin(),s.end() #define rall(s) s.rbegin(),s.rend() int min_cardinality(int n){ int d=0; set<int>st; for(int i=0;i<n;i++){ d++; move_inside(i); st.insert(i); int cnt=press_button(); if(cnt>1){ move_outside(i); st.erase(i); d--; } } for(auto i:st){ move_outside(i); } if(d<8){ vector<int>type(n,0); int ans=n; for(int i=1;i<=d;i++){ int cur=0; set<int>st; for(int j=0;j<n;j++){ if(type[j]==0){ move_inside(j); st.insert(j); cur++; int cnt=press_button(); if(cnt==cur){ type[j]=i; } else{ st.erase(j); cur--; move_outside(j); } } } ans=min(ans,(int)st.size()); for(auto j:st){ move_outside(j); } } return ans; } int l=1,r=n/d; while(l<r){ int mid=(l+r+1)/2; int len=0; st.clear(); for(int i=0;i<n;i++){ len++; move_inside(i); st.insert(i); int cnt=press_button(); if(cnt>mid){ len--; move_outside(i); st.erase(i); } } if(len==d*mid){ l=mid; } else{ r=mid-1; } for(auto i:st){ move_outside(i); } } return l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...