simplify parallel binary search

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)