結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー |
![]() |
提出日時 | 2020-02-14 21:39:50 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 65 ms / 2,000 ms |
コード長 | 2,094 bytes |
コンパイル時間 | 14,675 ms |
コンパイル使用メモリ | 377,420 KB |
実行使用メモリ | 8,932 KB |
最終ジャッジ日時 | 2024-11-16 00:29:41 |
合計ジャッジ時間 | 14,935 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
use std::io::Read; fn run_length_encoding<T: Clone + Eq>(a: &[T]) -> Vec<(T, usize)> { if a.len() == 0 { return vec![]; } let mut x = a[0].clone(); let mut cnt = 1; let mut ans = vec![]; for y in &a[1..] { if x == *y { cnt += 1; } else { ans.push((x, cnt)); x = y.clone(); cnt = 1; } } ans.push((x, cnt)); ans } fn gcd(a: u64, b: u64) -> u64 { if b == 0 { a } else { gcd(b, a % b) } } fn run() { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut it = s.trim().split_whitespace(); let h: usize = it.next().unwrap().parse().unwrap(); let w: usize = it.next().unwrap().parse().unwrap(); let k: u64 = it.next().unwrap().parse().unwrap(); let op = it.next().unwrap().chars().next().unwrap(); let mut b: Vec<u64> = (0..w).map(|_| it.next().unwrap().parse().unwrap()).collect(); let mut a: Vec<u64> = (0..h).map(|_| it.next().unwrap().parse().unwrap()).collect(); let ans = if op == '+' { for a in a.iter_mut().chain(b.iter_mut()) { *a %= k; } a.sort(); let a = run_length_encoding(&a); b.sort(); let b = run_length_encoding(&b); let mut ans = 0; for (a, x) in a.iter() { if let Ok(k) = b.binary_search_by(|p| p.0.cmp(&(k - a))) { ans += x * b[k].1; } } if a[0].0 == 0 && b[0].0 == 0 { ans += a[0].1 * b[0].1; } ans } else { for a in a.iter_mut().chain(b.iter_mut()) { *a = gcd(*a, k); } a.sort(); let a = run_length_encoding(&a); b.sort(); let b = run_length_encoding(&b); let mut ans = 0; for (a, x) in a.iter() { for (b, y) in b.iter() { if *a * *b % k == 0 { ans += x * y; } } } ans }; println!("{}", ans); } fn main() { run(); }