結果
問題 | No.262 面白くないビットすごろく |
ユーザー | not_522 |
提出日時 | 2015-08-06 23:36:19 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,821 bytes |
コンパイル時間 | 1,282 ms |
コンパイル使用メモリ | 159,876 KB |
実行使用メモリ | 7,552 KB |
最終ジャッジ日時 | 2024-07-18 03:47:44 |
合計ジャッジ時間 | 1,548 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
7,552 KB |
testcase_01 | AC | 5 ms
7,552 KB |
testcase_02 | AC | 5 ms
7,552 KB |
testcase_03 | AC | 4 ms
7,424 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> int least_bit(T n) { if (sizeof(T) == 4) return __builtin_ffs(n) - 1; if (sizeof(T) == 8) return __builtin_ffsll(n) - 1; assert(false); } template<typename T> int most_bit(T n) { if (sizeof(T) == 4) return n ? 31 - __builtin_clz(n) : -1; if (sizeof(T) == 8) return n ? 63 - __builtin_clzll(n) : -1; assert(false); } template<typename T> int count_bit(T n) { if (sizeof(T) == 4) return __builtin_popcount(n); if (sizeof(T) == 8) return __builtin_popcountll(n); assert(false); } int main() { typedef unsigned long long var; pair<var, int> dp[64][64][64]; for (int i = 0; i < 64; ++i) { for (int j = 0; j < 64; ++j) { if (i == 0 && j == 0) continue; var t = j; dp[6][i][j].first = 0; for (; t < 64; t += count_bit(t) + i) ++dp[6][i][j].first; dp[6][i][j].second = t - 64; } } for (int i = 7; i < 64; ++i) { for (int j = 0; j < 64; ++j) { for (int k = 0; k < 64; ++k) { if (j == 0 && k == 0) continue; auto f = dp[i - 1][j][k]; auto s = dp[i - 1][j + 1][f.second]; dp[i][j][k] = make_pair(f.first + s.first, s.second); } } } var n, m = 1, res = 1; cin >> n; for (int i = 6; i < 64; ++i) { if ((m & (1ull << i)) == 0) continue; int t = count_bit(m >> 6); auto s = dp[i][t][m % 64]; var l = m + (1ull << i) - m % 64 + s.second; if (l > n) continue; res += s.first; m = l; } for (int i = 63; i >= 6; --i) { int t = count_bit(m >> 6); auto s = dp[i][t][m % 64]; var l = m + (1ull << i) - m % 64 + s.second; if (l > n) continue; res += s.first; m = l; } while (m < n) { ++res; m += count_bit(m); } if (m == n) cout << res << endl; else cout << -1 << endl; }