結果

問題 No.3 ビットすごろく
コンテスト
ユーザー Quach Tri Dat
提出日時 2019-06-30 17:31:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 566 bytes
コンパイル時間 459 ms
コンパイル使用メモリ 42,624 KB
最終ジャッジ日時 2024-11-14 21:29:36
合計ジャッジ時間 944 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:7:12: error: 'scanf' was not declared in this scope
    7 |     int n; scanf("%d", &n);
      |            ^~~~~
main.cpp:16:8: error: 'printf' was not declared in this scope
   16 |     }; printf("%d\n", f[n] == INTFINITE ? -1 : f[n]);
      |        ^~~~~~
main.cpp:3:1: note: 'printf' is defined in header '<cstdio>'; did you forget to '#include <cstdio>'?
    2 | #include <queue>
  +++ |+#include <cstdio>
    3 | const int N = 10000;

ソースコード

diff # 

#include <array>
#include <queue>
const int N = 10000;
const int INTFINITE = 2147483647;
std::array<int, N + 1> f;
int main() {
    int n; scanf("%d", &n);
    f.fill(INTFINITE); f[1] = 1;
    std::queue<int> q; q.push(1);
    while (!q.empty() && f[n] == INTFINITE) {
        int x = q.front(); q.pop();
        int b = __builtin_popcount(x);
        int l = x - b, r = x + b;
        if (l && f[l] == INTFINITE) f[l] = f[x] + 1, q.push(l);
        if (r <= n && f[r] == INTFINITE) f[r] = f[x] + 1, q.push(r);
    }; printf("%d\n", f[n] == INTFINITE ? -1 : f[n]);
}
0