結果

問題 No.3 ビットすごろく
ユーザー iwotiwot
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0