tests/floor_sqrt.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)
• $\left\lfloor \sqrt{x} \right\rfloor$ (tools/floor_sqrt.hpp)

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include "tools/assert_that.hpp"
#include "tools/floor_sqrt.hpp"

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

  assert_that(tools::floor_sqrt(0) == 0);
  assert_that(tools::floor_sqrt(1) == 1);
  assert_that(tools::floor_sqrt(2) == 1);
  assert_that(tools::floor_sqrt(3) == 1);
  assert_that(tools::floor_sqrt(4) == 2);
  assert_that(tools::floor_sqrt(5) == 2);
  assert_that(tools::floor_sqrt(6) == 2);
  assert_that(tools::floor_sqrt(7) == 2);
  assert_that(tools::floor_sqrt(8) == 2);
  assert_that(tools::floor_sqrt(9) == 3);
  assert_that(tools::floor_sqrt(10) == 3);
  assert_that(tools::floor_sqrt(9223372030926249000) == 3037000498);
  assert_that(tools::floor_sqrt(9223372030926249001) == 3037000499);
  assert_that(tools::floor_sqrt(9223372030926249002) == 3037000499);
  assert_that(tools::floor_sqrt(9223372036854775807) == 3037000499);

  return 0;
}

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

#include <iostream>
#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_sqrt.hpp"



#include <cassert>

namespace tools {

  template <typename T>
  T floor_sqrt(const T n) {
    assert(n >= 0);

    T ok = 0;
    T ng;
    for (ng = 1; ng <= n / ng; ng *= 2);

    while (ng - ok > 1) {
      const T mid = ok + (ng - ok) / 2;
      if (mid <= n / mid) {
        ok = mid;
      } else {
        ng = mid;
      }
    }

    return ok;
  }
}


#line 6 "tests/floor_sqrt.test.cpp"

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

  assert_that(tools::floor_sqrt(0) == 0);
  assert_that(tools::floor_sqrt(1) == 1);
  assert_that(tools::floor_sqrt(2) == 1);
  assert_that(tools::floor_sqrt(3) == 1);
  assert_that(tools::floor_sqrt(4) == 2);
  assert_that(tools::floor_sqrt(5) == 2);
  assert_that(tools::floor_sqrt(6) == 2);
  assert_that(tools::floor_sqrt(7) == 2);
  assert_that(tools::floor_sqrt(8) == 2);
  assert_that(tools::floor_sqrt(9) == 3);
  assert_that(tools::floor_sqrt(10) == 3);
  assert_that(tools::floor_sqrt(9223372030926249000) == 3037000498);
  assert_that(tools::floor_sqrt(9223372030926249001) == 3037000499);
  assert_that(tools::floor_sqrt(9223372030926249002) == 3037000499);
  assert_that(tools::floor_sqrt(9223372036854775807) == 3037000499);

  return 0;
}

Back to top page