結果

問題 No.262 面白くないビットすごろく
コンテスト
ユーザー Min_25
提出日時 2015-08-01 12:08:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,539 bytes
コンパイル時間 649 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 00:22:09
合計ジャッジ時間 1,041 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cassert>

#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
#include <functional>
#include <vector>
#include <map>
#include <set>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

using namespace std;

typedef long long int64;
typedef long long unsigned uint64;
typedef long double float80;
typedef unsigned short uint16;
typedef unsigned uint;
typedef unsigned char uint8;

uint pops[1u << 16];

inline uint pop_count(uint n) {
  return pops[n & 65535] + pops[n >> 16];
}

const uint BITS = 40; // ceil(log2(10 ^ 12))
const uint pre = 6; // ceil(log2(BITS))
const uint pre_total = 1u << pre;

uint nsteps[BITS + 1][pre_total];
uint nexts[BITS + 1][pre_total];

uint64 nsteps2[BITS + 1][BITS + 2][BITS + 1];
uint nexts2[BITS + 1][BITS + 2][BITS + 1];

void init_pops() {
  for (uint i = 0; i < 16; ++i) {
    uint beg = 1 << i;
    uint end = beg << 1;
    for (uint j = beg; j < end; ++j) {
      pops[j] = pops[j - beg] + 1;
    }
  }
}

void init1() {
  for (int i = BITS; i >= 0; --i) {
    for (int j = pre_total - 1; j >= 0; --j) {
      uint k = j + i + pop_count(j);
      if (k >= pre_total) {
        nsteps[i][j] = 1;
        nexts[i][j] = k - pre_total;
      } else {
        nsteps[i][j] = nsteps[i][k] + 1;
        nexts[i][j] = nexts[i][k];
      }
    }
  }
}

void init2() {
  for (uint h = 0; h <= BITS; ++h) {
    for (uint l = 0; l <= BITS; ++l) {
      nsteps2[pre][h][l] = nsteps[h][l];
      nexts2[pre][h][l] = nexts[h][l];
    }
  }

  for (uint i = pre + 1; i <= BITS; ++i) {
    for (uint h = 0; h <= BITS; ++h) {
      for (uint l = 0; l <= BITS; ++l) {
        uint l2 = l;
        uint64 s = 0;
        s += nsteps2[i - 1][h][l2];
        l2 = nexts2[i - 1][h][l2];
        s += nsteps2[i - 1][h + 1][l2];
        l2 = nexts2[i - 1][h + 1][l2];
        nsteps2[i][h][l] = s;
        nexts2[i][h][l] = l2;
      }
    }
  }
}

void solve() {
  init_pops();
  init1();
  init2();

  uint64 n;
  while (~scanf("%llu", &n)) {
    uint64 nstep = 1;
    uint l = 1;
    uint pc_hi = 0;
    for (uint e = 63; e >= pre; --e) {
      uint64 mask = 1ull << e;
      if (mask <= n) {
        nstep += nsteps2[e][pc_hi][l];
        l = nexts2[e][pc_hi][l];
        pc_hi += 1;
        n -= mask;
      }
    }
    while (l < n) {
      l += pc_hi + pop_count(l);
      nstep += 1;
    }
    printf("%lld\n", l == n ? nstep : -1);
  }
}

int main() {
  solve();
  return 0;
}
0