結果
問題 |
No.3068 Speedrun (Hard)
|
ユーザー |
|
提出日時 | 2025-03-22 09:50:16 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,862 bytes |
コンパイル時間 | 13,950 ms |
コンパイル使用メモリ | 401,392 KB |
実行使用メモリ | 390,552 KB |
最終ジャッジ日時 | 2025-03-22 09:50:38 |
合計ジャッジ時間 | 18,176 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 TLE * 1 |
other | -- * 32 |
ソースコード
fn main() { // A1つをP分、 // B1つをQ分、 // C1つをR分、 // D1つをS分 // 半分全列挙で解く // AとBの組み合わせで作れる値AB、集合を管理 // CとDの組み合わせで作れる値CD、集合を管理 // ABを全探索、CDを二分探索で一致するものを取得 // 見つけたら、それぞれの集合の値を出力 let abcde : Vec<usize> = read_numbers_vec(5); let pqrst : Vec<usize> = read_numbers_vec(5); let mut ab_st = HashSet::new(); let mut ab_pair = HashMap::new(); for i in 0..=abcde[0] { // aだけでtを超過 let time_ab = pqrst[0] * i; if time_ab > pqrst[4] { break; } for j in 0..=abcde[1] { let time_ab = pqrst[0] * i + pqrst[1] * j; // aとbで超過 if time_ab > pqrst[4] { break; } if !ab_st.contains(&time_ab) { ab_st.insert(time_ab); ab_pair.insert(time_ab, (i, j)); } } } let mut vec_ab: Vec<_> = ab_st.into_iter().collect(); vec_ab.sort(); dbg!(vec_ab.len()); let mut cd_st = HashSet::new(); let mut cd_pair = HashMap::new(); for i in 0..=abcde[2] { // cだけで超過 let time_cd = pqrst[2] * i; if time_cd > pqrst[4] { break; } for j in 0..=abcde[3] { let time_cd = pqrst[2] * i + pqrst[3] * j; // dだけで超過 if time_cd > pqrst[4] { break; } if !cd_st.contains(&time_cd) { cd_st.insert(time_cd); cd_pair.insert(time_cd, (i, j)); } } } let mut vec_cd: Vec<_> = cd_st.into_iter().collect(); vec_cd.sort(); dbg!(vec_cd.len()); for pos_cd in 0..vec_cd.len() { let pos_ab = lower_bound(&vec_ab, pqrst[4] - vec_cd[pos_cd]); if pos_ab >= vec_ab.len() { continue;} // 値が一致 if vec_ab[pos_ab] + vec_cd[pos_cd] == pqrst[4] { let p_ab = *ab_pair.get(&vec_ab[pos_ab]).unwrap(); let p_cd = *cd_pair.get(&vec_cd[pos_cd]).unwrap(); // 選んだ個数が一致 if p_ab.0 + p_ab.1 + p_cd.0 + p_cd.1 == abcde[4] { println!("{} {} {} {}", p_ab.0, p_ab.1, p_cd.0, p_cd.1); return; } } } // 個々には来ない } // 二分探索 // x以上の最小のposを返す pub fn lower_bound<T: std::cmp::PartialOrd>(vec: &Vec<T>, val: T) -> usize { let mut l = 0; let mut r = vec.len(); while r - l > 0 { let m = (l + r) / 2; if vec[m] < val { l = m + 1; } else { r = m; } } l } // ---------- start input macro ---------- // const MOD17: usize = 1000000007; // const MOD93: usize = 998244353; // const INF: usize = 1 << 60; // let dx = vec![!0, 0, 1, 0]; // 上左下右 // let dy = vec![0, !0, 0, 1]; // 上左下右 // let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; // 上左下右 #[allow(unused)] use std::{ io, io::stderr, io::stdin, io::BufRead, io::Write, str::FromStr, mem::swap, cmp::min, cmp::max, cmp::Reverse, collections::HashSet, collections::BTreeSet, collections::HashMap, collections::BTreeMap, collections::BinaryHeap, collections::VecDeque, }; // usizeで受け取り #[allow(unused)] fn read_usize() -> usize { let mut input = String::new(); io::stdout().flush().unwrap(); // 出力バッファをフラッシュ io::stdin().read_line(&mut input).unwrap(); input.trim().parse().unwrap() } // 数値型を配列で受け取り #[allow(unused)] fn read_numbers_vec<T>(n: usize) -> Vec<T> where T: FromStr, <T as FromStr>::Err: std::fmt::Debug, { let mut input = String::new(); io::stdout().flush().unwrap(); io::stdin().read_line(&mut input).unwrap(); input.trim() .split_whitespace() // 空白区切りで分割 .take(n) // 指定された個数分だけ取り出す .map(|s| s.parse().unwrap()) // 各値をTに変換 .collect() // ベクターとして収集 } // char型配列で受け取り #[allow(unused)] fn read_char_array() -> Vec<char> { let mut input = String::new(); io::stdout().flush().unwrap(); io::stdin().read_line(&mut input).unwrap(); input.trim().chars().collect() } // 文字列型で受け取り #[allow(unused)] fn read_string() -> String { let mut input = String::new(); io::stdout().flush().unwrap(); io::stdin().read_line(&mut input).unwrap(); input.trim().to_string() } // 配列のスペース区切り出力 #[allow(unused)] fn vec_print<T: std::fmt::Display>(vec: &Vec<T>) { let sz = vec.len(); for i in 0..sz-1 { print!("{} ", vec[i]); } println!("{}", vec[sz-1]); } // ---------- end input macro ----------