#414060 (C++17) No.262 面白くないビットすごろく

提出ソース

結果

問題	No.262 面白くないビットすごろく
ユーザー	not_522
提出日時	2020-01-04 00:57:28
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	5 ms / 2,000 ms
コード長	7,510 bytes
コンパイル時間	1,022 ms
コンパイル使用メモリ	104,476 KB
実行使用メモリ	7,680 KB
最終ジャッジ日時	2024-05-02 07:49:09
合計ジャッジ時間	1,476 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 7,680 KB
testcase_01	AC	5 ms 7,552 KB
testcase_02	AC	5 ms 7,552 KB
testcase_03	AC	5 ms 7,552 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// This is free and unencumbered software released into the public domain.

// Anyone is free to copy, modify, publish, use, compile, sell, or
// distribute this software, either in source code form or as a compiled
// binary, for any purpose, commercial or non-commercial, and by any
// means.

// In jurisdictions that recognize copyright laws, the author or authors
// of this software dedicate any and all copyright interest in the
// software to the public domain. We make this dedication for the benefit
// of the public at large and to the detriment of our heirs and
// successors. We intend this dedication to be an overt act of
// relinquishment in perpetuity of all present and future rights to this
// software under copyright law.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

// For more information, please refer to <http://unlicense.org>

/****************/
/* template.hpp */
/****************/

#include <algorithm>
#include <cassert>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>

using std::cerr;
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::swap;

struct BoolName : std::numpunct<char> {
  std::string t, f;
  BoolName(std::string t, std::string f) : t(t), f(f) {}
  std::string do_truename() const { return t; }
  std::string do_falsename() const { return f; }
};

void setBoolName(std::string t, std::string f) {
  cout.imbue(std::locale(cout.getloc(), new BoolName(t, f)));
}

struct Initializer {
  Initializer() {
    cout << std::fixed << std::setprecision(15) << std::boolalpha;
    setBoolName("Yes", "No");
  }
} initializer;

struct Input {
  bool eof;

  Input() : eof(false) {}

  operator char() {
    char v;
    while (!(this->eof = (std::scanf("%c", &v) != 1)) && std::isspace(v)) {
    }
    return v;
  }

  operator int() {
    int v;
    this->eof = (std::scanf("%d", &v) != 1);
    return v;
  }

  operator long() {
    long v;
    this->eof = (std::scanf("%ld", &v) != 1);
    return v;
  }

  operator long long() {
    long long v;
    this->eof = (std::scanf("%lld", &v) != 1);
    return v;
  }

  operator unsigned int() {
    unsigned int v;
    this->eof = (std::scanf("%u", &v) != 1);
    return v;
  }

  operator unsigned long() {
    unsigned long v;
    this->eof = (std::scanf("%lu", &v) != 1);
    return v;
  }

  operator unsigned long long() {
    unsigned long long v;
    this->eof = (std::scanf("%llu", &v) != 1);
    return v;
  }

  operator double() {
    double v;
    this->eof = (std::scanf("%lf", &v) != 1);
    return v;
  }

  operator long double() {
    long double v;
    this->eof = (std::scanf("%Lf", &v) != 1);
    return v;
  }

  void ignore() const { getchar(); }
} in;

template <typename T> T abs(T a) { return a >= 0 ? a : -a; }

template <typename T, typename S> bool chmin(T &a, const S &b) {
  return a > b ? a = b, true : false;
}

template <typename T, typename S> bool chmax(T &a, const S &b) {
  return a < b ? a = b, true : false;
}

template <typename T, typename S> std::function<S(T)> cast() {
  return [](const T &t) { return static_cast<S>(t); };
}

template <typename T> T copy(const T &a) { return T(a); }

class ZeroPadding {
public:
  ZeroPadding(int n) : n(n) {}

  int n;
};

std::ostream &operator<<(std::ostream &os, const ZeroPadding &z) {
  os << std::setw(z.n) << std::setfill('0');
  return os;
}

template <typename T> constexpr T inf() {
  return std::numeric_limits<T>::max() / 2 - 1;
}

/*********************/
/* bit_operation.hpp */
/*********************/

template <typename T> int least_bit(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) {
    return __builtin_ffs(n) - 1;
  }
  if (sizeof(T) == 8) {
    return __builtin_ffsll(n) - 1;
  }
}

// n must be greater than 0.
template <typename T> int least_bit_fast(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) {
    return __builtin_ctz(n);
  }
  if (sizeof(T) == 8) {
    return __builtin_ctzll(n);
  }
}

template <typename T> int most_bit(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) {
    return n ? 31 - __builtin_clz(n) : -1;
  }
  if (sizeof(T) == 8) {
    return n ? 63 - __builtin_clzll(n) : -1;
  }
}

template <typename T> int count_bit(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) {
    return __builtin_popcount(n);
  }
  if (sizeof(T) == 8) {
    return __builtin_popcountll(n);
  }
}

template <typename T> int bit_parity(T n) {
  static_assert(sizeof(T) == 4 || sizeof(T) == 8, "unsupported size");
  if (sizeof(T) == 4) {
    return __builtin_parity(n);
  }
  if (sizeof(T) == 8) {
    return __builtin_parityll(n);
  }
}
/*************/
/* tuple.hpp */
/*************/

#include <tuple>

template <typename... T> class Tuple : public std::tuple<T...> {
public:
  Tuple(Input &in) : std::tuple<T...>() { (void)in; }
};

template <typename T, typename... S>
class Tuple<T, S...> : public std::tuple<T, S...> {
public:
  Tuple() : std::tuple<T, S...>() {}

  Tuple(T t, S... s) : std::tuple<T, S...>(t, s...) {}

  Tuple(const std::tuple<T, S...> &t) : std::tuple<T, S...>(t) {}

  Tuple(Input &in) {
    auto a = std::tuple<T>(in);
    std::tuple<S...> b = Tuple<S...>(in);
    std::tuple<T, S...> c = std::tuple_cat(a, b);
    *this = c;
  }

  template <int n> auto &get() { return std::get<n>(*this); }

  template <int n> const auto &get() const { return std::get<n>(*this); }
};

template <typename... T> Tuple<T...> makeTuple(const T &... args) {
  return Tuple<T...>(args...);
}

namespace std {
template <typename... T>
class tuple_size<Tuple<T...>>
    : public std::integral_constant<size_t, sizeof...(T)> {};
template <std::size_t I, typename... T> class tuple_element<I, Tuple<T...>> {
public:
  using type = tuple_element_t<I, std::tuple<T...>>;
};
} // namespace std

/************/
/* main.cpp */
/************/

int main() {
  Tuple<uint64_t, int> dp[64][64][64];
  for (int i = 0; i < 64; ++i) {
    for (int j = 0; j < 64; ++j) {
      if (i == 0 && j == 0) {
        continue;
      }
      uint64_t t = j;
      dp[6][i][j].get<0>() = 0;
      for (; t < 64; t += count_bit(t) + i) {
        ++dp[6][i][j].get<0>();
      }
      dp[6][i][j].get<1>() = t - 64;
    }
  }
  for (int i = 7; i < 64; ++i) {
    for (int j = 0; j < 64; ++j) {
      for (int k = 0; k < 64; ++k) {
        if (j == 0 && k == 0) {
          continue;
        }
        auto f = dp[i - 1][j][k];
        auto s = dp[i - 1][j + 1][f.get<1>()];
        dp[i][j][k] = makeTuple(f.get<0>() + s.get<0>(), s.get<1>());
      }
    }
  }
  uint64_t n(in), m = 1, res = 1;
  for (int i = 63; i >= 6; --i) {
    int t = count_bit(m >> 6);
    auto s = dp[i][t][m % 64];
    uint64_t l = m + (1ull << i) - m % 64 + s.get<1>();
    if (l > n) {
      continue;
    }
    res += s.get<0>();
    m = l;
  }
  while (m < n) {
    ++res;
    m += count_bit(m);
  }
  if (m == n) {
    cout << res << endl;
  } else {
    cout << -1 << endl;
  }
}

yukicoder

結果

テストケース

ソースコード