結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2016-11-20 13:24:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 646 bytes |
コンパイル時間 | 1,764 ms |
コンパイル使用メモリ | 172,496 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 08:10:24 |
合計ジャッジ時間 | 2,829 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; signed main(){ int N; cin >> N; queue< int > que; vector< int > dis( N + 1, ( int ) 1e9 ); que.emplace( 1 ); dis[ 1 ] = 1; while( not que.empty() ){ int u = que.front(); que.pop(); int nu = u + __builtin_popcount( u ); if( nu <= N and dis[ nu ] > dis[ u ] + 1 ) dis[ nu ] = dis[ u ] + 1, que.emplace( nu ); int pu = u - __builtin_popcount( u ); if( 1 <= pu and dis[ pu ] > dis[ u ] + 1 ) dis[ pu ] = dis[ u ] + 1, que.emplace( pu ); } if( dis[ N ] == ( int ) 1e9 ) cout << -1 << endl; else cout << dis[ N ] << endl; return 0; }