結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2020-10-15 15:06:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,755 bytes |
コンパイル時間 | 13,077 ms |
コンパイル使用メモリ | 382,020 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-20 19:45:34 |
合計ジャッジ時間 | 14,330 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 13 WA * 18 RE * 2 |
ソースコード
use std::collections::VecDeque; fn getline() -> String{ let mut __ret=String::new(); std::io::stdin().read_line(&mut __ret).ok(); return __ret; } fn main() { let n: usize = getline().trim().parse().unwrap(); // すごろくマス let mut masu: Vec<i32> = Vec::new(); // 現在の位置 let mut current_position: usize = 1; // キュー let mut queue: VecDeque<usize> = VecDeque::new(); // 1-Nのすごろくマスの初期化 for _ in 0..n { masu.push(-1); } masu[current_position - 1] = 1; queue.push_back(current_position); while !queue.is_empty() { // bitの1が立ってる数を取得 let bit_count_ones: usize = queue.pop_front().unwrap().count_ones() as usize; let pos = current_position - 1; if current_position - bit_count_ones > 0 && masu[pos - bit_count_ones] == -1 { // すごろくを前に進もうとする(マス内にいるか、まだとおっていないマスであれば、現在位置を更新する) masu[pos - bit_count_ones] = masu[pos] + 1; current_position = current_position - bit_count_ones; // キューに現在位置をpushする queue.push_back(current_position); } if current_position + bit_count_ones <= n && masu[pos + bit_count_ones] == -1 { // すごろくを後に進もうとする(ゴールより前かつまだ通っていないマス) masu[pos + bit_count_ones] = masu[pos] + 1; current_position = current_position + bit_count_ones; // キューに現在位置をpushする queue.push_back(current_position); } } println!("{}", masu[n - 1]); }