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>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
vector<int>V;
int n;
int solve(int l, int r, vector<int>czy) {
if(l==r) return l;
int mid=(l+r+1)/2;
vector<int>P;
rep(i, n) if(czy[i]) {
move_inside(i);
if(press_button()==mid+1) move_outside(i);
else P.pb(i);
}
bool ok=true;
for(auto i : V) {
move_inside(i);
if(press_button()==mid) ok=false;
move_outside(i);
}
if(ok) {
for(auto i : P) czy[i]=0;
return solve(mid, r, czy);
}
rep(i, n) czy[i]=0;
for(auto i : P) czy[i]=1;
for(auto i : P) move_outside(i);
return solve(l, mid-1, czy);
}
int min_cardinality(int _n) {
n=_n;
rep(i, n) {
move_inside(i);
if(press_button()==1) V.pb(i);
else move_outside(i);
}
vector<int>czy(n, 1);
for(auto i : V) czy[i]=0;
return solve(0, n, czy)+1;
//return solve(0, (n-V.size())/V.size(), czy)+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... |