#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N){
random_device rd;
mt19937 g(rd());
vector<bool> in(N, false);
int t = 0;
for (int i=0; i<N; i++){
move_inside(i);
in[i] = true;
t++;
if (press_button() > 1){
move_outside(i);
in[i] = false;
t--;
}
}
if (t == 1) return N;
int k = t;
int l = 1, r = N/t+1;
vector<int> w;
for (int i=0; i<N; i++) w.push_back(i);
while (l < r-1){
shuffle(w.begin(), w.end(), g);
vector<int> v;
int m = (l+r)/2;
for (int j=0; j<w.size(); j++){
if (k == t*m) break;
int i = w[j];
if (in[i]) continue;
move_inside(i);
in[i] = true;
k++;
if (press_button() > m){
move_outside(i);
in[i] = false;
k--;
}
else v.push_back(i);
}
if (k == t*m) l = m;
else {
r = m;
for (int x : v){
move_outside(x);
in[x] = false;
k--;
}
w = v;
}
}
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... |