結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2019-11-25 18:41:08 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 828 bytes |
コンパイル時間 | 585 ms |
コンパイル使用メモリ | 71,824 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:33:07 |
合計ジャッジ時間 | 1,699 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
// I SELL YOU...! #include<iostream> #include<vector> #include<algorithm> #include<functional> #include<queue> #define INF 1000000000 using namespace std; typedef long long ll; typedef pair<ll,ll> P; ll d[11000]; ll n; ll bc(ll v){ ll res=0; while(v>0){ if(v%2==1) res++; v>>=1; } return res; } signed main(){ ll next,ad; fill(d,d+11000,INF); cin >> n; priority_queue<P,vector<P>,greater<P>> que; que.push(P(1,1)); while(!que.empty()){ P tmp = que.top(); ll v=tmp.first,dis=tmp.second; que.pop(); if(d[v]<=dis){ continue; } d[v] = dis; ad = bc(v); dis++; next = v+ad; if(next<=n){ que.push(P(next,dis)); } next = v-ad; if(next>0){ que.push(P(next,dis)); } } if(d[n]==INF){ d[n]=-1; } cout << d[n]<<endl; }