結果

問題 No.3 ビットすごろく
ユーザー tamakorontamakoron
提出日時 2016-12-11 19:14:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,768 bytes
コンパイル時間 1,038 ms
コンパイル使用メモリ 90,824 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-05-06 18:40:36
合計ジャッジ時間 1,839 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 WA -
testcase_04 AC 2 ms
5,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 WA -
testcase_11 AC 1 ms
5,376 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 1 ms
5,376 KB
testcase_19 WA -
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 1 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 WA -
testcase_29 AC 1 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdint>
#include <cstdio>

// #include <cstdlib>

template <typename T, int LENGTH>
struct array
{
  T v[LENGTH];
  constexpr T& operator[](size_t l)
  { // accessor
    return v[l];
  }
  constexpr T const& operator[](size_t l) const
  { // accessor (allow writing)
    return v[l];
  }
};

constexpr int bitCount(uint32_t x)
{
  const uint32_t m1 = 0x55555555;
  const uint32_t m2 = 0x33333333;
  const uint32_t m4 = 0x0f0f0f0f;
  const uint32_t m8 = 0x00ff00ff;
  const uint32_t m16 = 0x0000ffff;
  const uint32_t m32 = 0xffffffff;
  x -= (x >> 1) & m1;
  x = (x & m2) + ((x >> 2) & m2);
  x = (x + (x >> 4)) & m4;
  x += x >> 8;
  x += x >> 16;
  return x & 0x7f;
}
template <typename T, int LEN>
constexpr array<T, LEN> gggg()
{
  auto vv = array<T, LEN>();
  vv[0] = 1;
  vv[1] = 1;
  vv[2] = 1;
  return vv;
}

template <typename T, int LEN>
constexpr array<array<T, 2>, LEN> init()
{
  auto aa = array<array<T, 2>, LEN>();
  auto buf = gggg<int, LEN>();
  int bufPos = 2;
  aa[1][1]=1;
  for (uint32_t i = 0; i < LEN; i++)
  {
    aa[i][0] = bitCount(i);
  }

  for (int i = 1; i < LEN; i++)
  {
    if (i >= bufPos)
    {
      break;
    }

    int plusMinus[2] = {(buf[i] + static_cast<int>(aa[buf[i]][0])),
                        (buf[i] - static_cast<int>(aa[buf[i]][0]))};
    for (int v : plusMinus)
    {
      if ((v < 1 || LEN <= v) || aa[v][1] != 0)
      {
        continue;
      }
      else
      {
        aa[v][1] = aa[buf[i]][1] + 1;
        buf[bufPos] = v;
        bufPos++;
      }
    }
  }
  return aa;
}

int main(int argc, char* argv[])
{
  constexpr auto ar = init<uint32_t, 10000>();
  int in;
  scanf("%d",&in);
  int ans = static_cast<int>(ar[in][1]);
  if(ans > in){
    ans = -1;
  }
  printf("%d",ans);
  return 0;
}
0