From 1abc08be606b7379bb1b9c5150bf73841a4b9c66 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Fri, 30 Aug 2024 16:46:50 +0200 Subject: improve pbs --- content/other/pbs.cpp | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'content/other/pbs.cpp') diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp index 5508d6c..6cf872a 100644 --- a/content/other/pbs.cpp +++ b/content/other/pbs.cpp @@ -1,10 +1,11 @@ // Q = # of queries, bucket sort is sometimes faster -vector low(Q, 0), high(Q, MAX_OPERATIONS); +vector low(Q, 0), high(Q, MAX_OPERATIONS + 1); while (true) { vector> 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)); @@ -14,5 +15,5 @@ while (true) { // simulation step } if (/* requirement already fulfilled */) high[i] = mid; - else low[i] = mid + 1; + else low[i] = mid; }} // answer in low (and high) -- cgit v1.2.3