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"
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |