結果
問題 | No.262 面白くないビットすごろく |
ユーザー | kimiyuki |
提出日時 | 2016-02-27 03:58:58 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 1,433 bytes |
コンパイル時間 | 706 ms |
コンパイル使用メモリ | 66,316 KB |
実行使用メモリ | 171,236 KB |
最終ジャッジ日時 | 2024-09-24 11:01:44 |
合計ジャッジ時間 | 2,095 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 206 ms
171,088 KB |
testcase_01 | AC | 209 ms
171,044 KB |
testcase_02 | AC | 209 ms
171,116 KB |
testcase_03 | AC | 207 ms
171,236 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) #define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i)) typedef long long ll; using namespace std; int main() { // input ll n; cin >> n; assert (n <= 1e12); const int l = 20; // log 10^12 < 40 const int mask = (1<<l) - 1; // make table vector<vector<int> > cnt(l, vector<int>(1<<l)); vector<vector<int> > bit(l, vector<int>(1<<l)); repeat (i,l) { repeat_reverse (j,1<<l) { int k = j + __builtin_popcount(j) + i; if (mask < k) { cnt[i][j] = 1; bit[i][j] = k & mask; } else { cnt[i][j] = 1 + cnt[i][k]; bit[i][j] = bit[i][k]; } } } // simulate ll ans = 1; ll ah = 0, al = 1; while (true) { int popcount_ah = __builtin_popcount(ah); ll bh = ah + 1; ll bl = bit[popcount_ah][al]; ll b = (bh << l) + bl; if (n < b) break; ans += cnt[popcount_ah][al]; ah = bh; al = bl; } int popcount_ah = __builtin_popcount(ah); ll nl = n & mask; while (al < nl) { ans += 1; al += popcount_ah + __builtin_popcount(al); } ll a = (ah << l) + al; if (a != n) ans = -1; // output cout << ans << endl; return 0; }