結果

問題 No.3 ビットすごろく
コンテスト
ユーザー tamakoron
提出日時 2016-12-11 19:47:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,865 bytes
コンパイル時間 895 ms
コンパイル使用メモリ 100,980 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-29 03:52:05
合計ジャッジ時間 1,751 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 26
権限があれば一括ダウンロードができます

ソースコード

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, 3>, LEN> init()
{
  auto aa = array<array<T, 3>, LEN>();
  auto buf = gggg<int, LEN>();
  int bufPos = 2;
  int max=0;
  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;
        aa[v][2] = aa[buf[i]][2] > v ? aa[buf[i]][2] : v;
        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 < static_cast<int>(ar[in][2])){
    ans = -1;
  }
  printf("%d",ans);
  return 0;
}
0