tests/floor_quotients.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)
• Enumerate the range of $\left\lfloor \frac{A}{x} \right\rfloor$ (tools/floor_quotients.hpp)

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include <vector>
#include <tuple>
#include <cassert>
#include <cstddef>
#include <algorithm>
#include <limits>
#include "tools/assert_that.hpp"
#include "tools/floor_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, 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::floor_quotients(A) == naive(A));
  }

  return 0;
}

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

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



#line 8 "tools/floor_quotients.hpp"

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

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

    return res;
  }
}


#line 12 "tests/floor_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, 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::floor_quotients(A) == naive(A));
  }

  return 0;
}

Back to top page