結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2023-03-15 13:45:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 5,000 ms |
コード長 | 1,109 bytes |
コンパイル時間 | 3,943 ms |
コンパイル使用メモリ | 254,404 KB |
最終ジャッジ日時 | 2025-02-11 11:36:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll inf=4444444444444444444; ll mod=1000000007; int main(){ ll n; cin >> n; queue<ll>que; vector<ll>memo(n+100,inf); memo[1]=1; vector<ll>two(30,1); for (ll i = 1; i < 30; i++) { two[i]=two[i-1]*2; } que.push(1); while (!que.empty()) { ll v=que.front(); que.pop(); ll x=0; for (ll i = 0; i < 30; i++) { if (two[i]&v) { x+=1; } } if (v-x>0) { if (memo[v-x]>memo[v]+1) { que.push(v-x); memo[v-x]=memo[v]+1; } } if (v+x<=n) { if (memo[v+x]>memo[v]+1) { que.push(v+x); memo[v+x]=memo[v]+1; } } } if (memo[n]==inf) { cout << -1 << endl; }else{ cout << memo[n] << endl; } }