#include "insects.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
vi inside(LIM,0);
int total = 0;
void add(int p) {
if (inside[p]) return;
inside[p] = 1;
total++;
move_inside(p);
}
void remove(int p) {
if (!inside[p]) return;
inside[p] = 0;
total--;
move_outside(p);
}
int D = 0;
vi placed;
vi skip(LIM,0);
bool check(int N,int x) {
placed.clear();
assert(total <= D*x);
for (int i = 0;i<N;i++) {
if (inside[i] || skip[i]) continue;
placed.push_back(i);
add(i);
int y = press_button();
if (y > x) {
placed.pop_back();
remove(i);
}
if (total == D*x) return true;
}
return false;
}
int min_cardinality(int N) {
for (int i = 0;i<N;i++) {
add(i);
int y = press_button();
if (y == 1) {
D++;
continue;
}
remove(i);
}
int l = 1;
int r = N/D;
while (l<=r) {
int m = (l+r) >> 1;
if (check(N,m)) l = m+1;
else {
for (auto it : placed) {
skip[it] = 1;
remove(it);
}
r = m-1;
}
}
return r;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |