# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
944687 | nguyentunglam | Rarest Insects (IOI22_insects) | C++17 | 104 ms | 856 KiB |
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;
const int NN = 1e5 + 10;
bool in[NN];
int min_cardinality(int n) {
int type = 0;
for(int i = 0; i < n; i++) {
move_inside(i);
if (press_button() == 1) {
++type;
in[i] = 1;
}
else move_outside(i);
}
int l = 1, r = n / type, ans = 1;
int cur = 1;
while (l < r) {
int mid = (l + r) / 2 + 1;
assert(cur <= mid);
vector<int> last_added;
int last = cur;
for(int i = 0; i < n; i++) if (!in[i]) {
in[i] = 1;
move_inside(i);
int nxt = press_button();
if (nxt > mid) {
move_outside(i);
in[i] = 0;
}
else {
cur = nxt;
last_added.push_back(i);
}
}
int total = 0;
for(int i = 0; i < n; i++) total += in[i];
if (cur == mid && mid * type == total) {
l = mid;
}
else {
r = mid - 1;
for(auto &j : last_added) {
move_outside(j);
in[j] = 0;
}
cur = last;
}
}
return l;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |