結果
問題 |
No.3244 Range Multiple of 8 Query
|
ユーザー |
![]() |
提出日時 | 2025-08-23 00:33:16 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 328 ms / 5,000 ms |
コード長 | 2,034 bytes |
コンパイル時間 | 15,735 ms |
コンパイル使用メモリ | 401,892 KB |
実行使用メモリ | 37,412 KB |
最終ジャッジ日時 | 2025-08-23 00:33:44 |
合計ジャッジ時間 | 18,480 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 40 |
ソースコード
use proconio::{ input, marker::{Bytes, Usize1}, }; use std::io::Write; fn main() { input! { _n: usize, q: usize, s: Bytes, queries: [(Usize1, usize); q] } let mut writer = std::io::BufWriter::new(std::io::stdout().lock()); let s = s.iter().map(|&d| (d - b'0') as usize).collect::<Vec<_>>(); let mut v = [!0usize; 10]; let mut prev = vec![]; for (i, &d) in s.iter().enumerate() { prev.push(v.clone()); v[d] = i; } prev.push(v); let mul8 = (0..1000) .step_by(8) .map(|mut x| { let a = x % 10; x /= 10; let b = x % 10; x /= 10; let c = x % 10; (c, b, a) }) .filter(|&(c, b, a)| a * b * c != 0) .collect::<Vec<_>>(); let mut right = [0; 10]; for &(l, r) in &queries { let mut ans = usize::MAX; if r - l == 1 { if s[l] == 0 || s[l] == 8 { ans = 0; } } else if r - l == 2 { let (a, b) = (s[l], s[l + 1]); if (a * 10 + b) % 8 == 0 { ans = 0; } else if (b * 10 + a) % 8 == 0 { ans = 1; } } else { for &(c, b, a) in &mul8 { right.fill(r); let i = prev[right[a]][a]; if i == !0 || i < l { continue; } right[a] = i; let j = prev[right[b]][b]; if j == !0 || j < l { continue; } right[b] = j; let k = prev[right[c]][c]; if k == !0 || k < l { continue; } let mut cand = 3 * r - 6 - i - j - k; cand += (i < j) as usize + (j < k) as usize + (i < k) as usize; ans = ans.min(cand); } } writeln!(writer, "{}", ans as isize).unwrap(); } }