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