結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2017-06-23 23:05:01 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,319 bytes |
コンパイル時間 | 986 ms |
コンパイル使用メモリ | 81,468 KB |
実行使用メモリ | 206,116 KB |
最終ジャッジ日時 | 2024-10-03 03:30:10 |
合計ジャッジ時間 | 7,534 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 TLE * 1 -- * 29 |
ソースコード
#include <iostream> #include <cstdio> #include <vector> #include <list> #include <map> #include <utility> #include <algorithm> #define rep(i, n) for(int (i)=0; (i)<(n); ++(i)) #define INF 1000000 using namespace std; int count_1(int n) { int x = 0; while(n > 0) { x += n % 2; n >>= 1; } return x; } typedef map<int, pair<int, int> > G; typedef map<int, bool> Visited; G create_matrix(int n) { G g; for(int i=1; i<=n; ++i) { int count = count_1(i); int a = i - count < 1 ? -1 : i - count; int b = i + count > n ? -1 : i + count; g[i] = pair<int, int>(a, b); } return g; } int walk(Visited& v, G g, int n, int x, int s) { if(x == n) { return s; } v[x] = true; int l = INF, r = INF; if(g[x].first != -1 && !v[g[x].first]) { l = walk(v, g, n, g[x].first, s+1); } if(g[x].second != -1 && !v[g[x].second]) { r = walk(v, g, n, g[x].second, s+1); } v[x] = false; return min(l, r); } Visited get_visited(int n) { Visited v; rep(i, n) { v[i+1] = false; } return v; } int main() { int n; cin >> n; Visited v = get_visited(n); G g = create_matrix(n); int r = walk(v, g, n, 1, 1); cout << (r == INF ? -1 : r) << endl; return 0; }