結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2019-07-24 12:44:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 619 bytes |
コンパイル時間 | 1,533 ms |
コンパイル使用メモリ | 170,800 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-01 09:26:47 |
合計ジャッジ時間 | 2,520 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;int n;void write(vector<int> &itr, vector<int> &q, int p, int d){if (p < 1 || p > n) return;if (p + d < 1 || p + d > n) return;if (itr.at(p + d - 1) == -1) {itr.at(p + d - 1) = itr.at(p - 1) + 1;q.push_back(p + d);}}int main(){cin >> n;vector<int> itr(n, -1), q;itr.at(0) = 1;q.push_back(1);for (int i = 0;; i++) {if (q.size() <= i) break;int p = q.at(i), d = bitset<32>(p).count();write(itr, q, p, d);write(itr, q, p, -d);}cout << itr.at(n - 1) << endl;}