haar_lib/algo/
parallel_binary_search.rs

1//! 並列二分探索
2//!
3//! # Problems
4//!
5//! - [CODE THANKS FESTIVAL 2017 H - Union Sets](https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/55116191)
6
7/// 並列二分探索
8pub fn parallel_binary_search(
9    m: usize,
10    q: usize,
11    mut init: impl FnMut(),
12    mut process: impl FnMut(usize),
13    mut checker: impl FnMut(usize) -> bool,
14) -> Vec<usize> {
15    let mut ok: Vec<isize> = vec![m as isize; q];
16    let mut ng: Vec<isize> = vec![-1; q];
17
18    loop {
19        let mut check = true;
20        let mut mids = vec![vec![]; m];
21
22        for (i, (ok, ng)) in ok.iter().zip(&ng).enumerate() {
23            if ok - ng > 1 {
24                check = false;
25                let mid = (ok + ng) / 2;
26                mids[mid as usize].push(i);
27            }
28        }
29
30        if check {
31            break;
32        }
33
34        init();
35
36        for (i, mid) in mids.iter().enumerate() {
37            process(i);
38            for &j in mid {
39                if checker(j) {
40                    ok[j] = i as isize;
41                } else {
42                    ng[j] = i as isize;
43                }
44            }
45        }
46    }
47
48    ok.into_iter().map(|x| x as usize).collect()
49}
haar_lib/algo/parallel_binary_search.rs

haar_lib/algo/
parallel_binary_search.rs
