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 <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
vector<int> memo(2000, -1);
bool check(int N, int mid, int uniqueValues) {
if (memo[mid] != -1) {
return memo[mid];
}
int amountInside = 0;
// cout << "Mid: " << mid << '\n';
// cout << press_button() << '\n';
vector<int> trackInside;
for (int i = 0; i < N; i++) {
move_inside(i);
amountInside++;
trackInside.push_back(i);
int curr = press_button();
if (curr > mid) {
move_outside(i);
amountInside--;
}
else if (curr == mid && amountInside == (uniqueValues * mid)) {
for (auto &i: trackInside) {
move_outside(i);
}
memo[mid] = true;
return true;
}
}
for (auto &i: trackInside) {
move_outside(i);
}
memo[mid] = false;
return false;
}
int min_cardinality(int N) {
vector<int> mask(N, false);
int uniqueValues = 0;
for (int i = 0; i < N; i++) {
move_inside(i);
if (press_button() == 1) {
mask[i] = true;
uniqueValues++;
continue;
}
else {
move_outside(i);
}
}
for (int i = 0; i < N; i++) {
if (mask[i] == true) {
move_outside(i);
}
// cout << mask[i] << ' ';
}
// cout << check(N, 1000, uniqueValues) << '\n';
// cout << check(N, 500, uniqueValues) << '\n';
int high = 2000;
int low = 0;
while (low <= high) {
int mid = (high + low) / 2;
// cout << low << ' ' << high << ' ' << mid << ' ' << check(N, mid, uniqueValues) << '\n';
if (low == high) {
return mid;
}
else {
if (check(N, mid, uniqueValues) && !check(N, mid + 1, uniqueValues)) {
return mid;
}
else if (check(N, mid, uniqueValues)) {
low = mid + 1;
}
else {
high = mid;
}
}
}
}
Compilation message (stderr)
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:44:30: warning: control reaches end of non-void function [-Wreturn-type]
44 | vector<int> mask(N, false);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |