結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2019-02-21 12:32:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,610 bytes |
コンパイル時間 | 2,016 ms |
コンパイル使用メモリ | 204,292 KB |
最終ジャッジ日時 | 2025-01-06 21:19:06 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include "bits/stdc++.h" using namespace std; using ll = long long; using ull = unsigned long long; using vb = vector<bool>; using vi = vector<int>; using vvi = vector<vector<int>>; using vl = vector<ll>; using vvl = vector<vector<ll>>; using pii = pair<int,int>; using pll = pair<ll,ll>; #define FOR(i,a,b) for(ll i = (a); i < (ll)(b); i++) #define REP(i,n) FOR(i,0,n) #define ALL(obj) (obj).begin(), (obj).end() #define rALL(obj) (obj).rbegin(), (obj).rend() #define eb(val) emplace_back(val) const double PI = acos(-1); const double EPS = 1e-10; const ll MOD = 1e9+7; const ll INF = 1e10; //#define int ll void cioacc(){//accelerate cin/cout cin.tie(0); ios::sync_with_stdio(false); } struct edge{ int to,cost; }; bool operator>(edge left,edge right){ return left.cost > right.cost; } using vve = vector<vector<edge>>; vl dijkstra(vve &gr,int st = 0){ int n = gr.size(); vl dist(n,INF); dist[st] = 0; priority_queue<pii,vector<pii>,greater<pii>> q; q.push(make_pair(dist[st]=0,st)); while(!q.empty()){ int now = q.top().second; q.pop(); REP(i,gr[now].size()){ edge &e = gr[now][i]; if(dist[now]+e.cost<dist[e.to]){ dist[e.to] = dist[now]+e.cost; q.push({dist[e.to],e.to}); } } } return dist; } signed main(){ int n; cin >> n; vve gr(n); REP(i,n){ int now = i+1; bitset<32> bits(i+1); int dis = (int)bits.count(); if(now-dis>=1) gr[i].emplace_back(edge{now-1-dis,1}); if(now+dis<=n) gr[i].emplace_back(edge{now-1+dis,1}); } auto dist = dijkstra(gr); cout << (dist[n-1]==INF?-1:dist[n-1]+1) << endl; }