結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2019-08-14 14:58:20 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,678 bytes |
コンパイル時間 | 11,257 ms |
コンパイル使用メモリ | 380,076 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 14:28:12 |
合計ジャッジ時間 | 13,220 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 WA * 10 |
ソースコード
fn read<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}fn main() {let n:u32 = read();#[derive(Debug, Clone)]struct Node {to: Vec<usize>,done: bool,cost: i32,}let mut nodes: Vec<Node> = vec![];for i in 1..=n {let prev_idx = i as i32 - 1 - i.count_ones() as i32;let next_idx = i as i32 - 1 + i.count_ones() as i32;let done = false;let cost = -1;let mut to = vec![];if prev_idx >= 0 {to.push(prev_idx as usize);}if next_idx < n as i32 {to.push(next_idx as usize);}nodes.push(Node{to, done, cost});}nodes[0].cost = 0;loop {let mut done_node_idx: Option<usize> = None;let max = nodes.len();for i in 0..max {if nodes[i].done || nodes[i].cost < 0 {continue;}if done_node_idx.is_none() || nodes[i].cost < nodes[done_node_idx.unwrap()].cost {done_node_idx = Some(i);}}if done_node_idx.is_none() {break;}// let done_node = &mut nodes[done_node_idx.unwrap()];nodes[done_node_idx.unwrap()].done = true;for toidx in nodes[done_node_idx.unwrap()].to.clone() {let cost = nodes[done_node_idx.unwrap()].cost + 1;if nodes[toidx].cost < 0 || cost < nodes[toidx].cost {nodes[toidx].cost = cost;}}}println!("{:?}", nodes[nodes.len()-1].cost + 1);}