blob: e6bfeac32208ddf20310fcb2dbc79514487696fc (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// Q = # of queries, bucket sort is sometimes faster
vector<int> low(Q, -1), high(Q, MAX_OPERATIONS);
while (true) {
vector<pair<int, int>> focus;
for (int i = 0; i < Q; i++) {
if (low[i] + 1 < high[i]) {
focus.emplace_back((low[i] + high[i]) / 2, i);
}}
if (focus.empty()) break;
ranges::sort(focus);
// reset simulation
for (int step = 0; auto [mid, i] : focus) {
for (; step <= mid; step++) {
// simulation step
}
if (/* requirement already fulfilled */) high[i] = mid;
else low[i] = mid;
}} // answer in low (MAX_OPERATIONS if never ok)
|
