結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2025-04-03 16:58:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 709 bytes |
コンパイル時間 | 1,321 ms |
コンパイル使用メモリ | 104,284 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-04-03 16:59:00 |
合計ジャッジ時間 | 2,847 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<queue> using namespace std; using ll =long long; void solve(){ ll N;cin >> N; vector<ll> ban(N+1,(1LL<<60)); ban[1]=0; queue<ll> que; que.push(1); while(!que.empty()){ ll a=que.front();que.pop(); if(a==N){ cout << ban[a]+1 << endl; return; } ll b=__popcount(a); if(a+b<=N&&ban[a+b]==(1LL<<60)){ ban[a+b]=ban[a]+1; que.push(a+b); } if(a-b>=0&&ban[a-b]==(1LL<<60)){ ban[a-b]=ban[a]+1; que.push(a-b); } } cout << -1 << endl; return; } int main(){ solve(); return 0; }