| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 938942 | irmuun | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,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;
}