tests/ceil_quotients.test.cpp

View this file on GitHub
Last update: 2025-02-10 01:30:13+09:00

Depends on

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include <vector>
#include <tuple>
#include <cassert>
#include <limits>
#include <cstddef>
#include <algorithm>
#include "tools/assert_that.hpp"
#include "tools/ceil.hpp"
#include "tools/ceil_quotients.hpp"

template <typename T>
std::vector<std::tuple<T, T, T>> naive(const T A) {
  assert(A >= 0);

  std::vector<std::tuple<T, T, T>> res;
  for (T x = 1; x <= A + 3; ++x) {
    res.emplace_back(x, x + 1, tools::ceil(A, x));
  }

  std::size_t vl = 0;
  for (std::size_t vr = 0, al = 0, ar = 0; al < res.size(); vl = vr, al = ar) {
    for (; ar < res.size() && std::get<2>(res[al]) == std::get<2>(res[ar]); ++vr, ++ar);
    if (vl < al) std::move(res.begin() + al, res.begin() + ar, res.begin() + vl);
    std::get<1>(res[vl]) = std::get<1>(res[vr - 1]);
    vr = vl + 1;
  }
  res.erase(res.begin() + vl, res.end());

  std::get<1>(res.back()) = std::numeric_limits<T>::max();
  return res;
}

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

  for (int A = 0; A <= 10000; ++A) {
    assert_that(tools::ceil_quotients(A) == naive(A));
  }

  return 0;
}

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

#include <iostream>
#include <vector>
#include <tuple>
#include <cassert>
#include <limits>
#include <cstddef>
#include <algorithm>
#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 1 "tools/ceil.hpp"



#line 5 "tools/ceil.hpp"
#include <type_traits>
#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 1 "tools/ceil_quotients.hpp"



#line 9 "tools/ceil_quotients.hpp"

namespace tools {
  template <typename T>
  ::std::vector<::std::tuple<T, T, T>> ceil_quotients(const T A) {
    assert(A >= 0);

    ::std::vector<::std::tuple<T, T, T>> res;
    if (A == 0) {
      res.emplace_back(1, ::std::numeric_limits<T>::max(), 0);
      return res;
    }

    T x;
    for (x = 1; x * x < A; ++x) {
      res.emplace_back(x, x + 1, ::tools::ceil(A, x));
    }
    for (T q = ::tools::ceil(A, x); q > 1; --q) {
      res.emplace_back((A - 1) / q + 1, (A - 1) / (q - 1) + 1, q);
    }
    res.emplace_back(A, ::std::numeric_limits<T>::max(), 1);

    return res;
  }
}


#line 13 "tests/ceil_quotients.test.cpp"

template <typename T>
std::vector<std::tuple<T, T, T>> naive(const T A) {
  assert(A >= 0);

  std::vector<std::tuple<T, T, T>> res;
  for (T x = 1; x <= A + 3; ++x) {
    res.emplace_back(x, x + 1, tools::ceil(A, x));
  }

  std::size_t vl = 0;
  for (std::size_t vr = 0, al = 0, ar = 0; al < res.size(); vl = vr, al = ar) {
    for (; ar < res.size() && std::get<2>(res[al]) == std::get<2>(res[ar]); ++vr, ++ar);
    if (vl < al) std::move(res.begin() + al, res.begin() + ar, res.begin() + vl);
    std::get<1>(res[vl]) = std::get<1>(res[vr - 1]);
    vr = vl + 1;
  }
  res.erase(res.begin() + vl, res.end());

  std::get<1>(res.back()) = std::numeric_limits<T>::max();
  return res;
}

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

  for (int A = 0; A <= 10000; ++A) {
    assert_that(tools::ceil_quotients(A) == naive(A));
  }

  return 0;
}