atcoder_nibutan.rs

mod nibutan{
    // bとuはinclusive
    pub fn true_false(b: i64, u: i64, f: &dyn Fn(i64)->bool) -> (Option<i64>, Option<i64>){
        assert!(b <= u);
        if f(b) == false{
            return (None, Some(b));
        }
        if f(u) == true{
            return (Some(u), None);
        }
        // f(b) = trueかつf(u) = false
        let mut b = b;
        let mut u = u;
        while (u - b).abs() > 1{
            let mid = (u + b)/2;
            if f(mid){
                b = mid;
            }else{
                u = mid;
            }
        }
        return (Some(b), Some(u));
    }

    pub fn false_true(b: i64, u: i64, f: &dyn Fn(i64)->bool) -> (Option<i64>, Option<i64>){
        return true_false(b, u, &|i|{!f(i)});
    }
}