結果

問題 No.3 ビットすごろく
コンテスト
ユーザー 달콤한마시로
提出日時 2026-01-13 20:47:04
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 17 ms / 5,000 ms
コード長 673 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 336 ms
コンパイル使用メモリ 41,848 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-13 20:47:07
合計ジャッジ時間 2,185 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
using std::scanf;
using std::printf;

using ll = long long;

int d[10101];
int v[10101];
int dist[10101];
int q[10101];

ll readint() { long long n; scanf("%lld", &n); return n; }

signed main() {
    for (int i = 1; i < 10101; ++i) d[i] = d[i/2] + i%2;
    int qe = 0;
    int qs = 0;
    int n = readint();
    auto push = [&](int i, int nd) {
        if (i < 1 || i > n) return;
        if (!v[i]) v[i] = 1, dist[i] = nd, q[qe++] = i;
    };
    dist[n] = -2;
    push(1, 0);
    while (qs < qe) {
        int i = q[qs++];
        push(i - d[i], dist[i] + 1);
        push(i + d[i], dist[i] + 1);
    }
    printf("%d\n", dist[n] + 1);
    return 0;
}
0