結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2022-10-16 23:16:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,110 bytes |
コンパイル時間 | 747 ms |
コンパイル使用メモリ | 78,356 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 16:44:52 |
合計ジャッジ時間 | 1,788 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <queue> using namespace std; using LL = long long; constexpr LL INF = 1L << 60; int sugoroku[10001]; int main() { int N; cin >> N; for (int i = 1; i <= N; i++) { if (sugoroku[i] == 0) { sugoroku[i] = sugoroku[i - 1] + 1; for (int j = i * 2; j <= N; j *= 2) { sugoroku[j] = sugoroku[i]; } } } vector<int> G[N + 1]; for (int i = 1; i <= N - 1; i++) { if (i + sugoroku[i] <= N) G[i].push_back(i + sugoroku[i]); if (i - sugoroku[i] >= 1) G[i].push_back(i - sugoroku[i]); } LL ans = INF; queue<pair<int, int>> que; que.emplace(1, 1); sugoroku[1] = 0; while (!que.empty()) { auto p = que.front(); que.pop(); if (p.first == N) { ans = p.second; break; } for (int q: G[p.first]) { if (sugoroku[q]) { que.emplace(q, p.second + 1); sugoroku[q] = 0; } } } cout << (ans != INF ? ans : -1) << endl; }