# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
631044 | gromperen | Rarest Insects (IOI22_insects) | C++17 | 64 ms | 460 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;
int min_cardinality(int N) {
vector<int> insects;
int cnt_uniq = 0;
for (int i = 0; i < N; ++i) {
move_inside(i);
if (press_button() == 1) cnt_uniq++;
else {
move_outside(i);
insects.push_back(i);
}
}
int ans = 1;
int low = 2, high = N/cnt_uniq;
while(low<=high) {
int mid = (low+high)/2;
vector<int> in, out;
for (int i : insects) {
move_inside(i);
if (press_button() > mid) {
move_outside(i);
out.push_back(i);
} else {
in.push_back(i);
}
}
if (in.size() == cnt_uniq * (mid-ans)) {
low = mid+1;
ans = mid;
insects = out;
} else {
high = mid-1;
insects = in;
for (auto i : in) move_outside(i);
}
}
return ans;
}
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... |