結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2021-01-02 20:08:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 965 bytes |
コンパイル時間 | 1,691 ms |
コンパイル使用メモリ | 174,384 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 10:01:34 |
合計ジャッジ時間 | 2,728 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(int)(n);i++)#define chmin(x,y) x = min((x),(y));#define chmax(x,y) x = max((x),(y));using namespace std;using ll = long long ;using P = pair<int,int> ;using pll = pair<long long,long long>;const int INF = 1e9;const long long LINF = 1e17;const int MOD = 1000000007;//const int MOD = 998244353;const double PI = 3.14159265358979323846;int main(){int n;cin >> n;vector<vector<int>> G(n+1);for(int i=1;i<=n;i++){int s = __builtin_popcount(i);if(i+s<=n) G[i].push_back(i+s);if(i-s>=1) G[i].push_back(i-s);}vector<int> seen(n+1,-1);queue<int> q;q.push(1);seen[1] = 1;while(!q.empty()){int now = q.front();q.pop();for(int nxt:G[now]){if(seen[nxt]>=0) continue;seen[nxt] = seen[now] + 1;q.push(nxt);}}cout << seen[n] << endl;return 0;}