This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "game/solve_partizan_game.hpp"
#include "game/dyadic_rational.hpp" // 全部 dyadic rational number になるときだけ解ける // 失敗したときは、empty map が返る // ・states:興味のある state 全体 // ・get_options:pair<vc<STATE>, vc<STATE>>(STATE), left ops / right ops template <typename STATE, typename INTEGER, typename F> unordered_map<STATE, Dyadic_Rational<INTEGER>> solve_partizan_game( const vector<STATE>& states, F get_options) { using X = Dyadic_Rational<INTEGER>; unordered_map<STATE, X> MP; bool success = 1; auto dfs = [&](auto& dfs, const STATE& s) -> X { if (!success) return X(); if (MP.count(s)) return MP[s]; vc<X> left, right; X xl = -X::infinity(), xr = X::infinity(); auto [left_ops, right_ops] = get_options(s); for (auto&& t: left_ops) chmax(xl, dfs(dfs, t)); for (auto&& t: right_ops) chmin(xr, dfs(dfs, t)); if (xl >= xr) { // switch success = 0; MP.clear(); return X(); } return (MP[s] = X::simplest(xl, xr)); }; for (auto&& s: states) dfs(dfs, s); return MP; }
#line 1 "game/dyadic_rational.hpp" // a+b/2^M の形で持つ template <typename INTEGER> struct Dyadic_Rational { using X = Dyadic_Rational; INTEGER a, b; static constexpr int M = std::numeric_limits<INTEGER>::digits - 2; Dyadic_Rational(INTEGER a = 0) : a(a), b(0) {} // x + y / z Dyadic_Rational(INTEGER x, INTEGER y, INTEGER z) : a(x), b(y) { auto [q, r] = divmod(b, z); a += q; b = r; b *= (INTEGER(1) << M) / z; } // x/y Dyadic_Rational(INTEGER x, INTEGER y) : Dyadic_Rational(0, x, y) {} static X from_ab(INTEGER a, INTEGER b) { X x(a); x.b = b; return x; } // 比較 bool operator==(X const& rhs) const { return (a == rhs.a && b == rhs.b); } bool operator!=(X const& rhs) const { return !(*this == rhs); } bool operator<(X const& rhs) const { return (a < rhs.a) || (a == rhs.a && b < rhs.b); } bool operator<=(X const& rhs) const { return (a < rhs.a) || (a == rhs.a && b <= rhs.b); } bool operator>(X const& rhs) const { return (a > rhs.a) || (a == rhs.a && b > rhs.b); } bool operator>=(X const& rhs) const { return (a > rhs.a) || (a == rhs.a && b >= rhs.b); } // 加法 friend X operator+(const X& x, const X& y) { INTEGER a = x.a + y.a, b = x.b + y.b; while (b >= INTEGER(1) << M) { ++a; b -= INTEGER(1) << M; } return from_ab(a, b); } friend X operator-(const X& x, const X& y) { INTEGER a = x.a - y.a, b = x.b - y.b; while (b < 0) { --a; b += INTEGER(1) << M; } return from_ab(a, b); } friend X operator-(const X& x) { INTEGER a = -x.a, b = -x.b; while (b < 0) { --a; b += INTEGER(1) << M; } return from_ab(a, b); } X& operator+=(const X& x) { return (*this) = (*this) + x; } X& operator-=(const X& x) { return (*this) = (*this) - x; } static X simplest(const X& x, const X& y) { assert(x < y); if (y.a < 0) return -simplest(-y, -x); { INTEGER l = x.a + 1; INTEGER r = (y.b == 0 ? y.a - 1 : y.a); if (l <= 0 && 0 <= r) return X(0); if (l <= r && 0 <= l) return X(l); if (l <= r && r <= 0) return X(r); } INTEGER l = x.b + 1; INTEGER r = (y.b == 0 ? (INTEGER(1) << M) - 1 : y.b - 1); if (l == r) return from_ab(x.a, l); int k = topbit(l ^ r); r &= ~((INTEGER(1) << k) - 1); return from_ab(x.a, r); } static constexpr X infinity() { return from_ab(INTEGER(1) << M, 0); } string to_string() { ll x = a, y = b, z = INTEGER(1) << M; while (y % 2 == 0 && z % 2 == 0) { y /= 2, z /= 2; } y += x * z; return std::to_string(y) + "/" + std::to_string(z); } }; #line 2 "game/solve_partizan_game.hpp" // 全部 dyadic rational number になるときだけ解ける // 失敗したときは、empty map が返る // ・states:興味のある state 全体 // ・get_options:pair<vc<STATE>, vc<STATE>>(STATE), left ops / right ops template <typename STATE, typename INTEGER, typename F> unordered_map<STATE, Dyadic_Rational<INTEGER>> solve_partizan_game( const vector<STATE>& states, F get_options) { using X = Dyadic_Rational<INTEGER>; unordered_map<STATE, X> MP; bool success = 1; auto dfs = [&](auto& dfs, const STATE& s) -> X { if (!success) return X(); if (MP.count(s)) return MP[s]; vc<X> left, right; X xl = -X::infinity(), xr = X::infinity(); auto [left_ops, right_ops] = get_options(s); for (auto&& t: left_ops) chmax(xl, dfs(dfs, t)); for (auto&& t: right_ops) chmin(xr, dfs(dfs, t)); if (xl >= xr) { // switch success = 0; MP.clear(); return X(); } return (MP[s] = X::simplest(xl, xr)); }; for (auto&& s: states) dfs(dfs, s); return MP; }