이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N){
random_device rd;
mt19937 g(rd());
vector<int> active;
int cnt = 0;
for (int i = 0; i < N; i++){
move_inside(i);
if (press_button() == 1) cnt++;
else{
move_outside(i); active.push_back(i);
}
}
shuffle(active.begin(), active.end(), g);
int ans = 1, l = 2, r = N / cnt, sz = cnt;
while (l <= r){
int m = (l + r) >> 1;
vector<int> iv, ov;
for (int i : active){
if (sz == cnt * m){
ov.push_back(i); continue;
}
move_inside(i);
if (press_button() <= m){
iv.push_back(i); sz++;
}
else{
move_outside(i); ov.push_back(i);
}
}
if (sz == cnt * m){
ans = m; l = m + 1;
active = ov;
}
else{
r = m - 1;
for (int i : iv) move_outside(i);
sz -= iv.size();
active = iv;
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |