shogo-library
競技プログラミング用の C++ ライブラリ
test/unittest/functions.test.cpp
- View this file on GitHub
- Last update: 2026-10-13 06:02:01+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
// functions.hpp の関数を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する
#include <algorithm>
#include <cmath>
#include <iostream>
#include <random>
#include "../../src/base/functions.hpp"
bool ok = true;
void check(bool cond, const char* what) {
if (!cond) {
if (ok) std::cerr << "failed: " << what << std::endl;
ok = false;
}
}
int main() {
std::mt19937_64 rng(314);
for (int rep = 0; rep < 20000 && ok; rep++) {
long long a = (long long)(rng() % 21) - 10, b = (long long)(rng() % 21) - 10;
// chmin / chmax: 更新したかを返す
{
long long x = a;
bool changed = chmin(x, b);
check(x == std::min(a, b) && changed == (b < a), "chmin");
x = a;
changed = chmax(x, b);
check(x == std::max(a, b) && changed == (b > a), "chmax");
double d = a;
check(chmin(d, b + 0.5) == (b + 0.5 < a) && d == std::min<double>(a, b + 0.5), "chmin (型が異なる)");
}
// long long 同士の max / min
check(max(a, b) == std::max(a, b) && min(a, b) == std::min(a, b), "max/min(long long, long long)");
check(max(a, 3) == std::max(a, 3LL) && min(2, b) == std::min(2LL, b), "max/min (int と long long の混在)");
// inrange / inrect
{
long long x = (long long)(rng() % 15) - 5;
check(inrange(x, a) == (0 <= x && x < a), "inrange(x, a)");
check(inrange(x, a, b) == (a <= x && x < b), "inrange(x, a, b)");
long long y = (long long)(rng() % 15) - 5;
check(inrect(x, y, a, b) == (0 <= x && x < a && 0 <= y && y < b), "inrect");
}
// 整数の二分探索: f(ok) が真、f(ng) が偽で単調なとき、境界の ok 側を返す
{
long long t = (long long)(rng() % 2001) - 1000;
long long lo = t - (long long)(rng() % 1000) - 1, hi = t + (long long)(rng() % 1000) + 1;
// f(x) = x <= t (ok = lo, ng = hi) -> t
check(binary_search(lo, hi, [&](long long x) { return x <= t; }) == t, "binary_search 整数 (ok < ng)");
// f(x) = x >= t (ok = hi, ng = lo) -> t
check(binary_search(hi, lo, [&](long long x) { return x >= t; }) == t, "binary_search 整数 (ok > ng)");
// 隣り合う ok, ng なら ok をそのまま返す
check(binary_search(t, t + 1, [&](long long) { return true; }) == t, "binary_search 整数 隣接");
}
// 実数の二分探索 (100 回)
{
double t = (double)(rng() % 2000001) / 1000.0; // [0, 2000]
double r = binary_search(0.0, 3000.0, [&](double x) { return x * x <= t; });
check(std::abs(r - std::sqrt(t)) < 1e-9, "binary_search 実数 sqrt");
double r2 = binary_search(3000.0, 0.0, [&](double x) { return x * x >= t; });
check(std::abs(r2 - std::sqrt(t)) < 1e-9, "binary_search 実数 (ok > ng)");
}
}
// 決まった値
check(binary_search(0, 1000000000, [](int x) { return (long long)x * x <= 1000000000; }) == 31622, "binary_search sqrt(1e9)");
check(!inrange(0, 0) && inrange(0, 1) && !inrange(-1, 1), "inrange 境界");
check(inrange(5, 5, 6) && !inrange(6, 5, 6), "inrange(x, a, b) 境界");
if (ok) std::cout << "Hello World" << std::endl;
}#line 1 "test/unittest/functions.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
// functions.hpp の関数を愚直な実装とランダムに比較する
// 問題の入力は使わず、すべて一致したら Hello World を出力する
#include <algorithm>
#include <cmath>
#include <iostream>
#include <random>
#line 2 "src/base/functions.hpp"
/**
* @file functions.hpp
* @brief 汎用関数 (chmin, chmax, 二分探索など)
*/
#line 9 "src/base/functions.hpp"
#include <array>
#line 11 "src/base/functions.hpp"
#include <numeric>
#line 2 "src/base/traits.hpp"
/**
* @file traits.hpp
* @brief 型特性
*/
#include <cstddef>
#include <iterator>
#include <set>
#include <type_traits>
#include <utility>
namespace detail {
using std::begin, std::end;
template <class T, class = void>
struct is_range_impl : std::false_type {};
template <class T>
struct is_range_impl<T, std::void_t<decltype(begin(std::declval<T&>()), end(std::declval<T&>()))>> : std::true_type {};
} // namespace detail
template <class T>
struct is_range : detail::is_range_impl<T>::type {};
template <class T>
inline constexpr bool is_range_v = is_range<T>::value;
#define HAS_METHOD(func_name) \
namespace detail { \
template <class T, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T> \
struct has_##func_name##_impl<T, std::void_t<decltype(std::declval<T>().func_name())>> \
: std::true_type {}; \
} \
template <class T> \
struct has_##func_name : detail::has_##func_name##_impl<T>::type {}; \
template <class T> \
inline constexpr bool has_##func_name##_v = has_##func_name<T>::value;
#define HAS_METHOD_ARG(func_name) \
namespace detail { \
template <class T, typename U, class = void> \
struct has_##func_name##_impl : std::false_type {}; \
template <class T, typename U> \
struct has_##func_name##_impl<T, U, std::void_t<decltype(std::declval<T>().func_name(std::declval<U>()))>> \
: std::true_type {}; \
} \
template <class T, typename U> \
struct has_##func_name : detail::has_##func_name##_impl<T, U>::type {}; \
template <class T, typename U> \
inline constexpr bool has_##func_name##_v = has_##func_name<T, U>::value;
HAS_METHOD(repr)
HAS_METHOD(type_str)
HAS_METHOD(initializer_str)
HAS_METHOD(max)
HAS_METHOD(min)
HAS_METHOD(reversed)
HAS_METHOD(sorted)
HAS_METHOD(sum)
HAS_METHOD(product)
HAS_METHOD(product_xor)
HAS_METHOD_ARG(count)
HAS_METHOD_ARG(find)
HAS_METHOD_ARG(lower_bound)
HAS_METHOD_ARG(upper_bound)
#define ENABLE_IF_T_IMPL(expr) std::enable_if_t<expr, std::nullptr_t> = nullptr
#define ENABLE_IF_T(...) ENABLE_IF_T_IMPL((__VA_ARGS__))
template <class C>
using mem_value_type = typename C::value_type;
template <class C>
using mem_difference_type = typename C::difference_type;
namespace detail {
template <class T, class = void>
struct is_sorted_container_impl : std::false_type {};
template <class T>
struct is_sorted_container_impl<std::set<T>> : std::true_type {};
template <class T>
struct is_sorted_container_impl<std::multiset<T>> : std::true_type {};
} // namespace detail
template <class T>
struct is_sorted_container : detail::is_sorted_container_impl<T>::type {};
template <class T>
inline constexpr bool is_sorted_container_v = is_sorted_container<T>::value;
#line 13 "src/base/functions.hpp"
template <typename T1, typename T2>
inline constexpr bool chmin(T1 &a, T2 b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <typename T1, typename T2>
inline constexpr bool chmax(T1 &a, T2 b) {
if (a < b) {
a = b;
return true;
}
return false;
}
inline constexpr long long max(const long long &t1, const long long &t2) {
return std::max<long long>(t1, t2);
}
inline constexpr long long min(const long long &t1, const long long &t2) {
return std::min<long long>(t1, t2);
}
using std::abs;
using std::gcd;
using std::lcm;
using std::size;
template <typename T>
constexpr T extgcd(const T &a, const T &b, T &x, T &y) {
T d = a;
if (b != 0) {
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
} else {
x = 1;
y = 0;
}
return d;
}
/**
* 偏角ソート
* 反時計回り
* x 軸正方向を始点とし、零ベクトルは x 軸正方向と同じ偏角として扱う
*/
template <typename T, ENABLE_IF_T(std::is_integral_v<T>)>
bool argcmp(std::array<T, 2> a, std::array<T, 2> b) {
// 零ベクトルは外積で比べられないので、偏角 0 (x 軸正方向) として先に判定する
const bool a_zero = a[0] == 0 && a[1] == 0;
const bool b_zero = b[0] == 0 && b[1] == 0;
if (b_zero) return false; // 偏角 0 より小さいものはない
if (a_zero) return !(b[1] == 0 && b[0] > 0); // b の偏角が 0 より大きいか
T a0 = std::array<T, 2>{a[1], a[0]} < std::array<T, 2>{0, 0};
T b0 = std::array<T, 2>{b[1], b[0]} < std::array<T, 2>{0, 0};
if (a0 < b0) {
return true;
} else if (b0 < a0) {
return false;
} else {
return b[0] * a[1] < a[0] * b[1];
}
}
template <typename M, typename N, class F, ENABLE_IF_T(std::is_integral_v<std::common_type_t<M, N>> and std::is_invocable_r_v<bool, F, std::common_type_t<M, N>>)>
inline constexpr std::common_type_t<M, N> binary_search(const M &ok, const N &ng, F f) {
std::common_type_t<M, N> _ok = ok, _ng = ng;
while (std::abs(_ok - _ng) > 1) {
std::common_type_t<M, N> mid = (_ok + _ng) / 2;
if (f(mid)) {
_ok = mid;
} else {
_ng = mid;
}
}
return _ok;
}
template <typename M, typename N, class F, ENABLE_IF_T(not std::is_integral_v<std::common_type_t<M, N>> and std::is_invocable_r_v<bool, F, std::common_type_t<M, N>>)>
inline constexpr std::common_type_t<M, N> binary_search(const M &ok, const N &ng, F f) {
std::common_type_t<M, N> _ok = ok, _ng = ng;
for (int i = 0; i < 100; i++) {
std::common_type_t<M, N> mid = (_ok + _ng) / 2;
if (f(mid)) {
_ok = mid;
} else {
_ng = mid;
}
}
return _ok;
}
/**
* 0 <= x < a
*/
inline constexpr bool inrange(long long x, long long a) {
return 0 <= x and x < a;
}
/**
* a <= x < b
*/
inline constexpr bool inrange(long long x, long long a, long long b) {
return a <= x and x < b;
}
/**
* 0 <= x < a and 0 <= y < b
*/
inline constexpr bool inrect(long long x, long long y, long long a, long long b) {
return 0 <= x and x < a and 0 <= y and y < b;
}
#line 12 "test/unittest/functions.test.cpp"
bool ok = true;
void check(bool cond, const char* what) {
if (!cond) {
if (ok) std::cerr << "failed: " << what << std::endl;
ok = false;
}
}
int main() {
std::mt19937_64 rng(314);
for (int rep = 0; rep < 20000 && ok; rep++) {
long long a = (long long)(rng() % 21) - 10, b = (long long)(rng() % 21) - 10;
// chmin / chmax: 更新したかを返す
{
long long x = a;
bool changed = chmin(x, b);
check(x == std::min(a, b) && changed == (b < a), "chmin");
x = a;
changed = chmax(x, b);
check(x == std::max(a, b) && changed == (b > a), "chmax");
double d = a;
check(chmin(d, b + 0.5) == (b + 0.5 < a) && d == std::min<double>(a, b + 0.5), "chmin (型が異なる)");
}
// long long 同士の max / min
check(max(a, b) == std::max(a, b) && min(a, b) == std::min(a, b), "max/min(long long, long long)");
check(max(a, 3) == std::max(a, 3LL) && min(2, b) == std::min(2LL, b), "max/min (int と long long の混在)");
// inrange / inrect
{
long long x = (long long)(rng() % 15) - 5;
check(inrange(x, a) == (0 <= x && x < a), "inrange(x, a)");
check(inrange(x, a, b) == (a <= x && x < b), "inrange(x, a, b)");
long long y = (long long)(rng() % 15) - 5;
check(inrect(x, y, a, b) == (0 <= x && x < a && 0 <= y && y < b), "inrect");
}
// 整数の二分探索: f(ok) が真、f(ng) が偽で単調なとき、境界の ok 側を返す
{
long long t = (long long)(rng() % 2001) - 1000;
long long lo = t - (long long)(rng() % 1000) - 1, hi = t + (long long)(rng() % 1000) + 1;
// f(x) = x <= t (ok = lo, ng = hi) -> t
check(binary_search(lo, hi, [&](long long x) { return x <= t; }) == t, "binary_search 整数 (ok < ng)");
// f(x) = x >= t (ok = hi, ng = lo) -> t
check(binary_search(hi, lo, [&](long long x) { return x >= t; }) == t, "binary_search 整数 (ok > ng)");
// 隣り合う ok, ng なら ok をそのまま返す
check(binary_search(t, t + 1, [&](long long) { return true; }) == t, "binary_search 整数 隣接");
}
// 実数の二分探索 (100 回)
{
double t = (double)(rng() % 2000001) / 1000.0; // [0, 2000]
double r = binary_search(0.0, 3000.0, [&](double x) { return x * x <= t; });
check(std::abs(r - std::sqrt(t)) < 1e-9, "binary_search 実数 sqrt");
double r2 = binary_search(3000.0, 0.0, [&](double x) { return x * x >= t; });
check(std::abs(r2 - std::sqrt(t)) < 1e-9, "binary_search 実数 (ok > ng)");
}
}
// 決まった値
check(binary_search(0, 1000000000, [](int x) { return (long long)x * x <= 1000000000; }) == 31622, "binary_search sqrt(1e9)");
check(!inrange(0, 0) && inrange(0, 1) && !inrange(-1, 1), "inrange 境界");
check(inrange(5, 5, 6) && !inrange(6, 5, 6), "inrange(x, a, b) 境界");
if (ok) std::cout << "Hello World" << std::endl;
}