結果

問題 No.3 ビットすごろく
コンテスト
ユーザー kichirb3
提出日時 2018-03-07 22:14:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,635 bytes
コンパイル時間 997 ms
コンパイル使用メモリ 95,372 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 08:56:51
合計ジャッジ時間 1,980 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// No.3 ビットすごろく
// https://yukicoder.me/problems/no/3
//

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <numeric>
using namespace std;

struct edge {
    int to;
    int cost;
};
typedef pair<int, int> P;
const int INF = 999999999;

int pop_count(unsigned int n);
vector<int> dijkstra(vector<edge>& adj, int s);


int pop_count(unsigned int n) {
    int res;
    __asm__( "popcnt %1, %0" : "=r"(res) : "r"(n) );
    return(res);
}


vector<int> dijkstra(vector<vector<edge>>& adj, int s)
{
    vector<int> d(adj.size()+1);
    priority_queue<P, vector<P>, greater<P>> que;
    fill(d.begin(), d.end(), INF );
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first)
            continue;
        for (int i = 0; i < adj[v].size(); ++i) {
            edge e = adj[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    return d;
}


int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<vector<edge>> adj;
    adj.resize(N+1);

    for (auto i = 1; i <= N; ++i) {
        int b = pop_count(i);
        if (i-b >= 1)
            adj[i].push_back({i-b, 1});
        if (i+b <= N)
            adj[i].push_back({i+b, 1});
    }

    vector<int> dist = dijkstra(adj, 1);
    if (dist[N] != INF)
        cout << dist[N] +1 << endl;
    else
        cout << -1 << endl;
}
0