結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2024-01-13 15:51:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,010 bytes |
コンパイル時間 | 779 ms |
コンパイル使用メモリ | 78,052 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-28 01:31:40 |
合計ジャッジ時間 | 1,619 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 19 | auto [d, x] = que.top(); | ^
ソースコード
// No.3 ビットすごろく #include <iostream> #include <vector> #include <bitset> #include <queue> using namespace std; const int INF = 1 << 30; int main() { int N; cin >> N; vector<int> dp(N, INF); dp[0] = 1; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que; que.push({1, 0}); while (!que.empty()) { auto [d, x] = que.top(); que.pop(); if (d > dp[x]) continue; int move = bitset<32>(x + 1).count(); if (x + move < N) { if (dp[x + move] > dp[x] + 1) { dp[x + move] = dp[x] + 1; que.push({dp[x + move], x + move}); } } if (x - move >= 0) { if (dp[x - move] > dp[x] + 1) { dp[x - move] = dp[x] + 1; que.push({dp[x - move], x - move}); } } } if (dp[N - 1] == INF) cout << -1 << endl; else cout << dp[N - 1] << endl; }