結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2024-11-12 13:22:57 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 494 ms / 5,000 ms |
コード長 | 967 bytes |
コンパイル時間 | 27,167 ms |
コンパイル使用メモリ | 374,336 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-12 13:23:30 |
合計ジャッジ時間 | 22,403 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
warning: type alias `Map` is never used --> src/main.rs:5:6 | 5 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: type alias `Set` is never used --> src/main.rs:6:6 | 6 | type Set<T> = BTreeSet<T>; | ^^^
ソースコード
use proconio::input; use std::collections::*; type Map<K, V> = BTreeMap<K, V>; type Set<T> = BTreeSet<T>; type Deque<T> = VecDeque<T>; fn main() { input! { n: usize } let inf = usize::MAX; let mut memo = vec![inf; n + 1]; memo[n] = 1; let mut que: Deque<usize> = Deque::new(); que.push_back(n); while !que.is_empty() { let v = que.pop_front().unwrap(); for x in 1..=n { let ones = x.count_ones() as usize; if x + ones == v { if memo[x] > memo[v] + 1 { memo[x] = memo[v] + 1; que.push_back(x); } } if x > ones && x - ones == v { if memo[x] > memo[v] + 1 { memo[x] = memo[v] + 1; que.push_back(x); } } } } if memo[1] != inf { println!("{}", memo[1]); }else { println!("-1"); } }