#184031 (D) No.262 面白くないビットすごろく

• 問題: No.262 面白くないビットすごろく
• ユーザー: te-sh
• 提出日時: 2017-06-26 17:03:24
• 言語: D (dmd 2.106.1)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 8,332 bytes
• コンパイル時間: 1,795 ms
• コンパイル使用メモリ: 144,000 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-12 20:30:54
• 合計ジャッジ時間: 2,332 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	5 ms; 6,940 KB
testcase_02	AC	5 ms; 6,940 KB
testcase_03	AC	5 ms; 6,944 KB

ソースコード

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto n = readln.chomp.to!long;

  auto p = 1, r = 0L;
  foreach (i; 0..(n >> 20)) {
    r += bi[i.popcnt][p];
    p = ai[i.popcnt][p];
  }

  auto c = (n >> 20).popcnt;
  auto d = n % (1 << 20);
  while (p < d) {
    ++r;
    p = p + p.popcnt + c;
  }

  if (p == d)
    writeln(r+1);
  else
    writeln(-1);
}

auto calc()
{
  auto ai = new int[][](21, 40);
  auto bi = new int[][](21, 40);

  auto m = (1 << 20);

  foreach (i; 0..21) {
    auto ci = new int[](m);
    auto di = new int[](m);

    foreach_reverse (j; 0..m) {
      auto k = j + j.popcnt + i;
      if (k >= m) {
        ci[j] = k - m;
        di[j] = 1;
      } else {
        ci[j] = ci[k];
        di[j] = di[k] + 1;
      }
    }

    ai[i][] = ci[0..40][];
    bi[i][] = di[0..40][];
  }

  writeln(ai);
  writeln(bi);
}

const ai = [[0,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3],[12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12],[10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],[10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],[3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3],[4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4],[8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13],[8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8],[7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12],[18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18,18],[14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14],[15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15],[35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35,35],[5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5],[20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20],[36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36],[20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20]];
const bi = [[1,108744,108743,108742,108742,108741,108741,108740,108740,108739,108739,108738,108738,108738,108737,108736,108737,108736,108736,108735,108735,108735,108734,108733,108734,108733,108733,108732,108732,108732,108732,108731,108732,108731,108731,108730,108730,108730,108729,108728],[98126,98125,98125,98124,98124,98124,98123,98122,98123,98122,98122,98121,98121,98121,98120,98120,98120,98120,98119,98119,98119,98118,98118,98118,98118,98117,98117,98117,98117,98116,98116,98115,98116,98116,98115,98115,98115,98114,98114,98114],[89307,89307,89306,89306,89306,89305,89305,89305,89305,89304,89304,89304,89304,89303,89303,89302,89303,89302,89302,89302,89302,89301,89301,89301,89301,89301,89300,89300,89300,89300,89300,89299,89300,89299,89299,89299,89299,89298,89298,89296],[81965,81964,81964,81964,81964,81963,81963,81962,81963,81962,81962,81962,81962,81961,81961,81961,81961,81961,81961,81960,81960,81960,81960,81960,81959,81959,81959,81959,81959,81958,81959,81958,81958,81959,81958,81957,81957,81958,81958,81957],[75801,75801,75801,75800,75800,75800,75800,75800,75800,75799,75800,75799,75799,75799,75799,75798,75799,75798,75798,75798,75798,75798,75798,75797,75797,75798,75797,75797,75797,75797,75796,75796,75797,75796,75796,75796,75796,75796,75795,75795],[70585,70585,70585,70585,70585,70584,70584,70584,70584,70584,70584,70583,70583,70583,70583,70583,70583,70583,70583,70582,70582,70582,70582,70582,70582,70582,70582,70581,70581,70581,70581,70581,70581,70581,70581,70580,70580,70579,70580,70580],[66148,66148,66148,66149,66149,66147,66147,66147,66147,66147,66147,66148,66148,66146,66146,66146,66146,66146,66146,66147,66147,66147,66145,66145,66146,66145,66145,66146,66146,66145,66146,66144,66145,66144,66144,66144,66144,66145,66144,66144],[62310,62310,62309,62309,62309,62309,62309,62309,62309,62309,62308,62308,62308,62308,62308,62308,62308,62308,62308,62307,62307,62307,62307,62307,62307,62307,62307,62307,62307,62306,62306,62306,62306,62306,62306,62306,62306,62305,62306,62305],[58881,58881,58881,58881,58881,58880,58881,58880,58880,58880,58880,58880,58880,58880,58880,58879,58880,58879,58879,58879,58879,58879,58879,58879,58879,58879,58879,58878,58878,58878,58878,58878,58878,58878,58878,58878,58878,58878,58878,58877],[55740,55740,55740,55740,55740,55740,55740,55739,55739,55739,55739,55739,55739,55739,55739,55739,55739,55739,55738,55738,55738,55738,55738,55738,55738,55738,55738,55738,55738,55737,55737,55737,55737,55737,55737,55737,55737,55737,55737,55737],[52878,52878,52877,52877,52877,52877,52877,52877,52877,52877,52877,52877,52877,52876,52876,52876,52876,52876,52876,52876,52876,52876,52876,52875,52876,52875,52875,52875,52875,52875,52875,52875,52875,52875,52875,52875,52875,52874,52874,52874],[50326,50326,50326,50326,50326,50325,50325,50325,50325,50325,50325,50325,50325,50325,50325,50325,50325,50325,50324,50324,50324,50324,50324,50324,50324,50324,50324,50324,50324,50324,50324,50323,50324,50323,50323,50323,50323,50323,50323,50323],[48062,48062,48062,48062,48062,48062,48062,48062,48062,48061,48062,48061,48061,48061,48061,48061,48061,48061,48061,48061,48061,48061,48061,48060,48061,48060,48060,48060,48060,48060,48060,48060,48060,48060,48060,48060,48060,48060,48060,48059],[45990,45990,45990,45990,45990,45990,45989,45989,45990,45989,45989,45989,45989,45989,45989,45989,45989,45989,45989,45989,45989,45988,45989,45988,45988,45988,45988,45988,45988,45988,45988,45988,45988,45988,45988,45988,45988,45987,45988,45987],[44043,44043,44043,44043,44043,44043,44043,44043,44043,44043,44043,44042,44042,44042,44042,44042,44042,44042,44042,44042,44042,44042,44042,44042,44042,44042,44042,44041,44041,44041,44041,44041,44041,44041,44041,44041,44041,44041,44041,44041],[42249,42249,42249,42249,42249,42249,42249,42249,42249,42249,42249,42249,42249,42248,42249,42248,42249,42248,42248,42248,42248,42248,42248,42248,42248,42248,42248,42248,42248,42248,42248,42247,42248,42248,42247,42247,42247,42247,42247,42247],[40625,40625,40625,40625,40625,40623,40625,40623,40623,40623,40623,40623,40623,40623,40624,40624,40624,40624,40624,40624,40624,40624,40624,40622,40624,40622,40622,40622,40622,40622,40622,40623,40622,40623,40623,40623,40623,40623,40623,40623],[39098,39098,39098,39103,39103,39103,39103,39103,39103,39103,39102,39097,39097,39102,39097,39097,39097,39097,39097,39097,39097,39102,39102,39102,39102,39102,39102,39102,39102,39101,39101,39096,39101,39101,39096,39096,39096,39096,39096,39096],[37612,37612,37613,37612,37612,37612,37613,37613,37613,37611,37611,37611,37611,37611,37611,37611,37611,37611,37611,37611,37611,37612,37611,37611,37611,37611,37612,37612,37612,37610,37610,37610,37610,37610,37610,37610,37610,37610,37610,37610],[36195,36195,36195,36195,36195,36195,36195,36195,36195,36195,36194,36195,36195,36195,36195,36195,36195,36195,36194,36194,36194,36194,36194,36194,36194,36194,36194,36194,36194,36194,36194,36193,36194,36194,36193,36194,36194,36194,36194,36193],[34919,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34918,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917,34917]];

pragma(inline) {
  import core.bitop;
  pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); }
}