結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2014-11-16 01:30:31 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 973 bytes |
コンパイル時間 | 565 ms |
コンパイル使用メモリ | 65,484 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:06:13 |
合計ジャッジ時間 | 1,572 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <cstdio> #include <queue> #define mp std::make_pair typedef std::pair<int,int> P; int N; int main(){ std::cin >> N; int res = -1, minT[10001]; std::fill(minT, minT+10001, 1001001001); std::queue<P> q; q.push(mp(1, 1)); minT[1] = 1; while(!q.empty()){ P p = q.front(); q.pop(); if(p.second > minT[p.first]){continue;} if(p.first == N){res = p.second; break;} int bc = __builtin_popcount(p.first); if(p.first + bc <= N && p.second+1 < minT[p.first+bc]){ minT[p.first+bc] = p.second+1; q.push(mp(p.first+bc, p.second+1)); } if(1 <= p.first - bc && p.second+1 < minT[p.first-bc]){ minT[p.first-bc] = p.second+1; q.push(mp(p.first-bc, p.second+1)); } } if(res == -1){ puts("-1"); }else{ printf("%d\n", res); } }