tests/logn_integer_partition.test.cpp

• View this file on GitHub
• Last update: 2025-01-25 08:45:50+09:00

Depends on

• Assertion macro (tools/assert_that.hpp)
• Multiset $S$ such that $\{\sum_{x \in S'} x | S' \subseteq S\} = \{0, 1, \ldots, N\}$ and $|S| = O(\log N)$ (tools/logn_integer_partition.hpp)
• $2^x$ (tools/pow2.hpp)

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include <vector>
#include <cstddef>
#include <algorithm>
#include <numeric>
#include "tools/logn_integer_partition.hpp"
#include "tools/pow2.hpp"
#include "tools/assert_that.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  for (int n = 0; n < 32; ++n) {
    const auto parts = tools::logn_integer_partition(n);

    std::vector<int> sumset;
    for (std::size_t state = 0; state < tools::pow2(parts.size()); ++state) {
      int sum = 0;
      for (std::size_t i = 0; i < parts.size(); ++i) {
        if (state & (1 << i)) {
          sum += parts[i];
        }
      }
      sumset.push_back(sum);
    }
    std::sort(sumset.begin(), sumset.end());
    sumset.erase(std::unique(sumset.begin(), sumset.end()), sumset.end());

    std::vector<int> expected(n + 1);
    std::iota(expected.begin(), expected.end(), 0);

    assert_that(sumset == expected);
  }

  return 0;
}

#line 1 "tests/logn_integer_partition.test.cpp"
// competitive-verifier: STANDALONE

#include <iostream>
#include <vector>
#include <cstddef>
#include <algorithm>
#include <numeric>
#line 1 "tools/logn_integer_partition.hpp"



#line 5 "tools/logn_integer_partition.hpp"
#include <cassert>

namespace tools {
  template <typename T>
  ::std::vector<T> logn_integer_partition(T n) {
    assert(n >= 0);
    ::std::vector<T> res;
    for (T pow2 = 1; pow2 < n; n -= pow2, pow2 *= 2) {
      res.push_back(pow2);
    }
    if (n > 0) res.push_back(n);
    return res;
  }
}


#line 1 "tools/pow2.hpp"



#include <type_traits>
#line 6 "tools/pow2.hpp"

namespace tools {

  template <typename T, typename ::std::enable_if<::std::is_unsigned<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(1) << x;
  }

  template <typename T, typename ::std::enable_if<::std::is_signed<T>::value, ::std::nullptr_t>::type = nullptr>
  constexpr T pow2(const T x) {
    return static_cast<T>(static_cast<typename ::std::make_unsigned<T>::type>(1) << static_cast<typename ::std::make_unsigned<T>::type>(x));
  }
}


#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 11 "tests/logn_integer_partition.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  for (int n = 0; n < 32; ++n) {
    const auto parts = tools::logn_integer_partition(n);

    std::vector<int> sumset;
    for (std::size_t state = 0; state < tools::pow2(parts.size()); ++state) {
      int sum = 0;
      for (std::size_t i = 0; i < parts.size(); ++i) {
        if (state & (1 << i)) {
          sum += parts[i];
        }
      }
      sumset.push_back(sum);
    }
    std::sort(sumset.begin(), sumset.end());
    sumset.erase(std::unique(sumset.begin(), sumset.end()), sumset.end());

    std::vector<int> expected(n + 1);
    std::iota(expected.begin(), expected.end(), 0);

    assert_that(sumset == expected);
  }

  return 0;
}

Back to top page