이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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... |