結果
問題 |
No.3067 +10 Seconds Clock
|
ユーザー |
|
提出日時 | 2025-03-22 08:40:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,672 bytes |
コンパイル時間 | 14,825 ms |
コンパイル使用メモリ | 377,948 KB |
実行使用メモリ | 7,320 KB |
最終ジャッジ日時 | 2025-03-22 08:41:10 |
合計ジャッジ時間 | 15,777 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 WA * 1 |
ソースコード
fn main() { // 先頭から取るタイマーを決め打ち二分探索 // nn:地点、tt:開始の残り時間 let nt: Vec<usize> = read_numbers_vec(2); let nn = nt[0]; let tt = nt[1]; // tは地点間の距離 let t: Vec<usize> = read_numbers_vec(nn-1); // xはタイマー地点(タイマがある箇所を10とする) let k: usize = read_usize(); let xpos: Vec<usize> = read_numbers_vec(k); let mut x = vec![0; nn]; for xx in xpos { x[xx] = 10; } // タイマーの取得個数を二分探索 let mut ng = -1 as i64; let mut ok = (k+1) as i64; for _ in 0..50 { // 取るタイマーの個数を決める let mid = (ok + ng) / 2; // スタートからゴールまで行けるか判定 if enabled_move(nn, tt, &t, &x, mid as usize) { ok = mid; } else { ng = mid; } } if ok as usize == k+1 { println!("-1"); } else { println!("{}", ok); } } fn enabled_move(nn: usize, tt: usize, dt: &Vec<usize>, x:&Vec<usize>, get_cnt: usize) -> bool { let mut cur_time = tt; // 残り取得タイマー数 let mut t_cnt = get_cnt; for i in 0..nn-1 { // 移動不可 if cur_time <= dt[i] { return false; } // 移動 cur_time -= dt[i]; // 移動後の座標でタイマー取得 if t_cnt > 0 && x[i+1] > 0 { cur_time += 10; t_cnt -= 1; } } true } // ---------- 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 ----------