diff options
Diffstat (limited to 'content/other/pbs.cpp')
| -rw-r--r-- | content/other/pbs.cpp | 16 |
1 files changed, 8 insertions, 8 deletions
diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 7cb60e5..f4db2fd 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,19 +1,19 @@ // Q = # of queries, bucket sort is sometimes faster -vector<int> low(Q, 0), high(Q, MAX_OPERATIONS); +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] < high[i]) { - focus.emplace_back((low[i] + high[i]) / 2, i); - } + 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; sort(all(focus)); // reset simulation for (int step = 0; auto [mid, i] : focus) { - while (step <= mid) { + for (; step <= mid; step++) { // simulation step - step++; } if (/* requirement already fulfilled */) high[i] = mid; - else low[i] = mid + 1; -}} // answer in low (and high) + else low[i] = mid; +}} // answer in low (MAX_OPERATIONS if never ok) |