結果
| 問題 | No.260 世界のなんとか3 |
| ユーザー |
 uAutDnLD5Pe5QqV
|
| 提出日時 | 2019-02-05 21:24:33 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
MLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,308 bytes |
| コンパイル時間 | 15,777 ms |
| コンパイル使用メモリ | 380,172 KB |
| 実行使用メモリ | 65,024 KB |
| 最終ジャッジ日時 | 2025-01-03 00:08:32 |
| 合計ジャッジ時間 | 19,406 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 MLE * 6 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:81:5 | 81 | mut eight_remainder: usize, | ----^^^^^^^^^^^^^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default
ソースコード
use std::io::BufRead;pub struct StdinReader<R: BufRead> {pub buf_reader: R,pub buf: String,}impl<R: BufRead> StdinReader<R> {pub fn new(r: R) -> Self {StdinReader {buf_reader: r,buf: String::with_capacity(10000),}}}#[macro_export]macro_rules! input {($reader : expr, $t : ty) => { // one variablematch &mut $reader {reader => {use std::io::BufRead;reader.buf_reader.read_line(&mut reader.buf).unwrap();let tmp_var: $t = reader.buf.trim().parse().unwrap();reader.buf.clear();tmp_var},}};($reader : expr, $t0 : ty, $t1 : ty) => { // 2 tuplematch &mut $reader {reader => {use std::io::BufRead;reader.buf_reader.read_line(&mut reader.buf).unwrap();let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();reader.buf.clear();(tmp_var[0].clone(), tmp_var[1].clone())}}};($reader : expr, $t0 : ty, $t1 : ty, $t2 : ty) => { // 3 tuplematch &mut $reader {reader => {use std::io::BufRead;reader.buf_reader.read_line(&mut reader.buf).unwrap();let tmp_var: Vec<$t0> = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();reader.buf.clear();(tmp_var[0], tmp_var[1], tmp_var[2])}}};($reader : expr, $t : ty; $size : expr) => { // Vectormatch &mut $reader {reader => {use std::io::BufRead;reader.buf_reader.read_line(&mut reader.buf).unwrap();let tmp_var: $t = reader.buf.trim().split_whitespace().map(|a| a.parse().unwrap()).collect();reader.buf.clear();tmp_var}}};}type Memo = Vec<Vec<Vec<Vec<Vec<Option<usize>>>>>>;fn main() {let handle = std::io::stdin();let mut r = StdinReader::new(handle.lock());let (a_str, b_str): (String, String) = input!(r, String, String);let (a, b): (Vec<char>, Vec<char>) = (a_str.chars().collect(), b_str.chars().collect());// now_digit -> eight mod -> three mod -> is there three -> strict (lower || upper || lower && upper || all ok)let mut memo: Memo = vec![vec![vec![vec![vec![None; 4]; 2]; 3]; 8]; b.len()];println!("{}", dp(b.len() - 1, 0, 0, 0, 2, &a, &b, &mut memo));}const STRICT: usize = 1000000007;fn dp(now_d: usize,mut eight_remainder: usize,three_remainder: usize,exist_three: usize,state: usize,a: &Vec<char>,b: &Vec<char>,memo: &mut Memo) -> usize {if let Some(ans) = memo[now_d][eight_remainder][three_remainder][exist_three][state] {return ans;}let mut ans = 0;let a_n: usize = a.iter().rev().nth(now_d).unwrap_or(&'0').to_digit(10).unwrap() as usize;let b_n: usize = b.iter().rev().nth(now_d).unwrap().to_digit(10).unwrap() as usize;let mut lower = 0;let mut upper = 10; // not includeif state == 0 {lower = a_n;} else if state == 1 {upper = b_n + 1;} else if state == 2 {lower = a_n;upper = b_n + 1;} else if state == 3 {// all ok// do nothing} else { panic!("I dont know state{}!!!", state); }if now_d == 0 {ans += (lower..upper).into_iter().filter(|i| (exist_three == 1 || *i == 3 || (three_remainder + (i % 3)) % 3 == 0) && (eight_remainder + (i % 8)) % 8 != 0).count();ans %= STRICT;} else {if state == 0 {for i in lower..upper {let mut now_eight_remainder = eight_remainder;if now_d < 3 {now_eight_remainder += i * (10 as usize).pow(now_d as u32);now_eight_remainder %= 8;}let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };if i == a_n {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 0, a, b, memo);ans %= STRICT;} else {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);ans %= STRICT;}}} else if state == 1 {for i in lower..upper {let mut now_eight_remainder = eight_remainder;if now_d < 3 {now_eight_remainder += i * (10 as usize).pow(now_d as u32);now_eight_remainder %= 8;}let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };if i == b_n {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 1, a, b, memo);ans %= STRICT;} else {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);ans %= STRICT;}}} else if state == 2 {for i in lower..upper {let mut now_eight_remainder = eight_remainder;if now_d < 3 {now_eight_remainder += i * (10 as usize).pow(now_d as u32);now_eight_remainder %= 8;}let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };if a_n == b_n {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 2, a, b, memo);ans %= STRICT;} else if i == a_n {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 0, a, b, memo);ans %= STRICT;} else if i == b_n {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 1, a, b, memo);ans %= STRICT;} else {ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);ans %= STRICT;}}} else if state == 3 {for i in lower..upper {let mut now_eight_remainder = eight_remainder;if now_d < 3 {now_eight_remainder += i * (10 as usize).pow(now_d as u32);now_eight_remainder %= 8;}let now_exist_three = if exist_three == 1 || i == 3 { 1 } else { 0 };ans += dp(now_d-1, now_eight_remainder, (three_remainder + (i % 3)) % 3, now_exist_three, 3, a, b, memo);ans %= STRICT;}} else { panic!("I dont know state{}!!!", state); }}memo[now_d][eight_remainder][three_remainder][exist_three][state] = Some(ans);return ans;}