結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2025-03-01 15:38:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,472 bytes |
コンパイル時間 | 3,497 ms |
コンパイル使用メモリ | 280,668 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-03-01 15:38:29 |
合計ジャッジ時間 | 4,953 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> #include <cassert> #define YES cout<<"Yes"<<endl; #define NO cout<<"No"<<endl; #define nall(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using vl = vector<ll>; using vvl = vector<vector<ll>>; using vvvl = vector<vector<vector<ll>>>; //sample vvvl A(N,vvl(N,vl(N,0))); const ll POW2=1e2,POW5=1e5,POW6=1e6,POW9=1e9,POW12=1e12,POW15=1e15,POW18=1e18; const int iINF = 1<<30; const ll INF = 1LL<<62; const ull UINF = 1LL<<63; const ld ldINF=(ld)POW15; const ll mod=998244353; const ll mod2=1000000007; const ld PI=3.141592653589793238462643; vector<ll> dy={-1,0,1,0},dx={0,1,0,-1},dy8={-1,-1,-1,0,0,1,1,1},dx8={-1,0,1,-1,1,-1,0,1}; template<class T> using pq = priority_queue<T,vector<T>>; template<class T> using pq_g = priority_queue<T,vector<T>,greater<T>>; template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } template<class T>void vc_unique(vector<T> &v){v.erase(unique(v.begin(),v.end()),v.end());} template<class T>void sdebug(string s, T& a){cout<<s<<": "<<a<<endl;} template<class T>void vdebug(string s, vector<T> &v){ ll W=v.size(); cout<<"--------------------------"<<endl; cout<<s<<": "<<endl; for(ll i=0;i<W;i++){ if(v[i]>POW15) cout<<"INF "; else if(v[i]<-POW15) cout<<"-INF "; else cout<<v[i]<<" "; } cout<<endl; } template<class T>void vvdebug(string s, vector<vector<T>> &v){ ll H=v.size(); cout<<"--------------------------"<<endl; cout<<s<<": "<<endl; for(ll i=0;i<H;i++){ for(auto e:v[i]){ if(e>POW15) cout<<"INF "; else if(e<-POW15) cout<<"-INF "; else cout<<e<<" "; } cout<<endl; } } ll roundUp(ll n, ll m){ if(n>=0 && n%m!=0) return n/m+1; else return n/m; } ll truncate(ll n, ll m){ if(n<0 && n%m!=0) return n/m-1; else return n/m; } int main() { std::cin.tie(0)->sync_with_stdio(0); ll N;cin>>N; queue<ll> q; vl dist(N+1,INF); q.push(1); dist[1]=1; while(!q.empty()){ ll pos=q.front();q.pop(); ll p=__builtin_popcount(pos); if(pos+p<=N && dist[pos+p]==INF){ dist[pos+p]=dist[pos]+1; q.push(pos+p); } if(pos-p>0 && dist[pos-p]==INF){ dist[pos-p]=dist[pos]+1; q.push(pos-p); } } if(dist[N]==INF) cout<<-1<<endl; else cout<<dist[N]<<endl; }