diff options
| -rw-r--r-- | other/pbs.cpp | 47 |
1 files changed, 17 insertions, 30 deletions
diff --git a/other/pbs.cpp b/other/pbs.cpp index 45577e2..7cb60e5 100644 --- a/other/pbs.cpp +++ b/other/pbs.cpp @@ -1,32 +1,19 @@ -// Q = Anzahl der Anfragen -// C = Anzahl der Schritte der Operation - -vector<vector<int>> focus; -vector<int> low, high, ans; - -ans.assign(Q, C + 1); -low.assign(Q, 0); -high.assign(Q, C); -focus.assign(C + 1, vector<int>()); -for (bool changed = true; changed;) { - changed = false; - for (int i = 0; i <= C; i++) focus[i].clear(); - for (int i = 0; i < Q; i++) { - if (low[i] > high[i]) continue; - focus[(low[i] + high[i]) / 2].pb(i); +// Q = # of queries, bucket sort is sometimes faster +vector<int> low(Q, 0), 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); } + if (focus.empty()) break; + sort(all(focus)); - // Simulation zurücksetzen - - for (int k = 0; k <= C; k++) { - // Simulationsschritt - - for (int q : focus[k]) { - changed = true; - if (/* Eigenschaft schon erfüllt */) { - // Antwort updaten - high[q] = k - 1; - ans[q] = min(ans[q], k); - } else { - low[q] = k + 1; -}}}} + // reset simulation + for (int step = 0; auto [mid, i] : focus) { + while (step <= mid) { + // simulation step + step++; + } + if (/* requirement already fulfilled */) high[i] = mid; + else low[i] = mid + 1; +}} // answer in low (and high) |