Submission #60108583

---

Source Code Expand

use itertools::Itertools;
use proconio::{input, marker::{Chars, Usize1}};


fn to_index(c: char) -> usize {
    match c {
        '/' => 0,
        '1' => 1,
        '2' => 2,
        _ => unreachable!(),
    }
}

fn judge(v: &Vec<Vec<usize>>, m: usize, l: usize, r: usize) -> bool {
    /* 長さ2*m+1の部分文字列があるか */
    let mut idx = l;
    if m != 0 {
        let k = v[1].lower_bound(idx);
        if k + m - 1 >= v[1].len() {
            return false;
        }
        idx = v[1][k + m - 1];
    }

    {
        let k = v[0].lower_bound(idx);
        if k >= v[0].len() {
            return false;
        }
        idx = v[0][k];
    }

    if m != 0 {
        let k = v[2].lower_bound(idx);
        if k + m - 1 >= v[2].len() {
            return false;
        }
        idx = v[2][k + m - 1];
    }

    if idx <= r {
        true
    } else {
        false
    }

}

fn main() {
    input!{
        n: usize,
        q: usize,
        s: Chars,
    }


    let mut v = vec![vec![]; 3];
    for (i, &c) in s.iter().enumerate() {
        v[to_index(c)].push(i);
    }
    dbg!(&v);

    for _ in 0..q {
        input! {
            l: Usize1,
            r: Usize1,
        }

        let mut ok = !0;
        let mut ng = r-l+1;

        while ng.wrapping_sub(ok) > 1 {
            let m = ng.wrapping_add(ok) / 2;
            if judge(&v, m, l, r) {
                ok = m;
            } else {
                ng = m;
            }
        }
        if ok == !0 {
            println!("0");
        } else {
            println!("{}", ok * 2 + 1);
        }
    }
}


pub trait VecLibs<T: std::cmp::Ord> {
    fn lower_bound(&self, elm: T) -> usize;
    fn upper_bound(&self, elm: T) -> usize;
}

impl<T: std::cmp::Ord> VecLibs<T> for Vec<T> {
    fn lower_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] < elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }

    fn upper_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] <= elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }
}

Submission Info

Compile Error

warning: unused import: `itertools::Itertools`
 --> src/main.rs:1:5
  |
1 | use itertools::Itertools;
  |     ^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `n`
  --> src/main.rs:51:9
   |
51 |         n: usize,
   |         ^ help: if this is intentional, prefix it with an underscore: `_n`
   |
   = note: `#[warn(unused_variables)]` on by default

Judge Result