結果
問題 | No.3 ビットすごろく |
ユーザー | morinaga |
提出日時 | 2020-02-16 15:38:06 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,372 bytes |
コンパイル時間 | 513 ms |
コンパイル使用メモリ | 54,720 KB |
実行使用メモリ | 8,832 KB |
最終ジャッジ日時 | 2024-10-06 14:31:24 |
合計ジャッジ時間 | 6,980 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
ソースコード
#include <stdio.h> #include <ctype.h> #include <stdlib.h> #include <algorithm> #include <vector> #define INF 1000000 using namespace std; int is_reachable(int idx, vector<int> squares, vector<int> footprint) { if (any_of(footprint.begin(), footprint.end(), [idx](int x) { return x == idx; })) { /* for (auto p : footprint) { printf("%d->", p); } printf("%d", idx); */ return INF; } footprint.push_back(idx); if (idx == 0) { return 1; } int fastest = INF; for (int i = 0; i < squares.size(); i++) { if (i + squares[i] == idx || i - squares[i] == idx) { int route = 1 + is_reachable(i, squares, footprint); if (route < fastest) { fastest = route; } } } return fastest; } int main() { int n; scanf("%d", &n); vector<int> squares(n, 0); for (int i = 0; i < n; i++) { unsigned int v = i + 1; unsigned int c; for (c = 0; v; v >>= 1) { c += v & 1; } squares[i] = c; } vector<int> footprint{}; int answer = is_reachable(n - 1, squares, footprint); if (answer >= INF) { printf("-1"); } else { printf("%d", answer); } }