結果

問題 No.3244 Range Multiple of 8 Query
コンテスト
ユーザー LyricalMaestro
提出日時 2026-01-06 23:09:14
言語 Rust
(1.92.0 + proconio + num)
結果
AC  
実行時間 899 ms / 5,000 ms
コード長 4,192 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 26,252 ms
コンパイル使用メモリ 411,452 KB
実行使用メモリ 20,432 KB
最終ジャッジ日時 2026-01-06 23:10:00
合計ジャッジ時間 44,312 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;

fn get_last_three_values_digits() -> Vec<[u8; 3]> {
    let mut v = Vec::new();
    // Pythonでは i in range(1000), if i%8==0 で i0=1000+i の下3桁を見ている
    // 下3桁は 000..999（先頭0含む）になりうるので %1000 で取り、各桁0を弾く
    for i in (0..1000).step_by(8) {
        let i0 = 1000 + i;
        let x = i0 % 1000; // 下3桁
        let a = (x / 100) as u8;
        let b = ((x / 10) % 10) as u8;
        let c = (x % 10) as u8;
        if a != 0 && b != 0 && c != 0 {
            v.push([a, b, c]);
        }
    }
    v
}

fn solve_length1(ch: u8) -> i64 {
    if ch == b'8' { 0 } else { -1 }
}

fn solve_length2(s: &[u8]) -> i64 {
    // ひっくり返さない場合
    let a = (s[0] - b'0') as i32;
    let b = (s[1] - b'0') as i32;
    let x = a * 10 + b;
    if x % 8 == 0 {
        return 0;
    }
    // ひっくり返す場合
    let y = b * 10 + a;
    if y % 8 == 0 { 1 } else { -1 }
}

fn solve_length3(
    prev_pos: &Vec<Vec<i32>>,
    last_three_values: &Vec<[u8; 3]>,
    l: usize,
    r: usize,
) -> i64 {
    let mut best: i64 = i64::MAX;

    for digits in last_three_values.iter() {
        let mut ans: i64 = 0;

        let mut target_index: isize = r as isize;
        let mut used: Vec<usize> = Vec::with_capacity(3);
        let mut ok = true;

        // Python: for ideal_digit in reversed(ideal_value)
        // digits = [a,b,c] なので reversed は c,b,a
        for &d in [digits[2], digits[1], digits[0]].iter() {
            if target_index < 0 {
                ok = false;
                break;
            }
            let mut ind: i32 = prev_pos[d as usize][target_index as usize];
            // while l < ind and ind in used_index:
            while ind != -1 && (l as i32) < ind && used.contains(&(ind as usize)) {
                let pi = ind as usize;
                if pi == 0 {
                    ind = -1;
                    break;
                }
                ind = prev_pos[d as usize][pi - 1];
            }

            if ind < l as i32 || ind == -1 || used.contains(&(ind as usize)) {
                ok = false;
                break;
            }

            let ind_u = ind as usize;
            let t_u = target_index as usize;

            // w = count(used_index i where ind <= i <= target_index)
            let w = used.iter().filter(|&&i| ind_u <= i && i <= t_u).count() as i64;

            // ans += target_index - ind - w
            ans += (t_u as i64) - (ind_u as i64) - w;

            used.push(ind_u);

            // while target_index in used_index: target_index -= 1
            while target_index >= 0 && used.contains(&(target_index as usize)) {
                target_index -= 1;
                // target_index が l を下回っても、次の digit の探索で自然に失敗するのでそのまま
            }
        }

        if ok {
            if ans < best {
                best = ans;
            }
        }
    }

    if best == i64::MAX { -1 } else { best }
}

fn main() {
    input! {
        n: usize,
        q: usize,
        s: String,
        lr: [(usize, usize); q],
    }

    let bytes = s.as_bytes();

    // 3桁以上の場合、下３桁が以下のようになっていればOK（Pythonの get_last_three_values 相当）
    let last_three_values = get_last_three_values_digits();

    // seg_tree_list 相当: prev_pos[d][i] = i 以下で数字 d が最後に出た位置（なければ -1）
    let mut prev_pos: Vec<Vec<i32>> = vec![vec![-1; n]; 10];
    for d in 0..10 {
        let mut last_i: i32 = -1;
        for i in 0..n {
            if bytes[i] == b'0' + (d as u8) {
                last_i = i as i32;
            }
            prev_pos[d][i] = last_i;
        }
    }

    let mut out = String::new();
    for (l1, r1) in lr {
        let l = l1 - 1;
        let r = r1 - 1;

        let res = if r == l {
            solve_length1(bytes[l])
        } else if r == l + 1 {
            solve_length2(&bytes[l..=r])
        } else {
            solve_length3(&prev_pos, &last_three_values, l, r)
        };

        out.push_str(&format!("{}\n", res));
    }

    print!("{}", out);
}
0