結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2020-02-16 17:13:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,200 bytes |
コンパイル時間 | 454 ms |
コンパイル使用メモリ | 54,016 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 09:41:02 |
合計ジャッジ時間 | 1,534 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <stdio.h> #include <vector> #include <queue> #define UKN -1 using namespace std; int main() { int n; scanf("%d", &n); vector<int> squares(n, 0); for (int i = 0; i < n; i++) { unsigned int v = i + 1; unsigned int c; for (c = 0; v; v >>= 1) { c += v & 1; } squares[i] = c; } vector<int> least_steps(n, UKN); least_steps[0] = 1; queue<int> reachable_sqs; reachable_sqs.push(0); int goal_idx = n - 1; while (!reachable_sqs.empty()) { int cur_idx = reachable_sqs.front(); reachable_sqs.pop(); int propulsion = squares[cur_idx]; if (cur_idx + propulsion <= goal_idx && least_steps[cur_idx + propulsion] == UKN) { least_steps[cur_idx + propulsion] = least_steps[cur_idx] + 1; reachable_sqs.push(cur_idx + propulsion); } if (cur_idx - propulsion >= 0 && least_steps[cur_idx - propulsion] == UKN) { least_steps[cur_idx - propulsion] = least_steps[cur_idx] + 1; reachable_sqs.push(cur_idx - propulsion); } } printf("%d", least_steps[goal_idx]); }