結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2016-02-29 01:09:28 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 784 bytes |
コンパイル時間 | 560 ms |
コンパイル使用メモリ | 69,296 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:45:49 |
合計ジャッジ時間 | 1,524 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> pii; int n; void bfs(vector<int> &block, int s){ block[s] = 1; queue<pii> que; que.push(pii(2, s)); int cnt; while(not que.empty()){ s = que.front().second; cnt = que.front().first; int w = __builtin_popcount(s); que.pop(); if(s - w >= 1 and block[s - w] > cnt){ block[s - w] = cnt; que.push(pii(cnt + 1, s - w)); } if(n >= s + w and block[s + w] > cnt){ block[s + w] = cnt; que.push(pii(cnt + 1, s + w)); } } } int main(){ std::cin >> n; vector<int> block(n + 1, 1e9); bfs(block, 1); if(block[n] != 1e9)std::cout << block[n] << std::endl; else std::cout << -1 << std::endl; return 0; }