library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:question: game/number_and_star.hpp

Depends on

Required by

Verified with

Code

#include "game/dyadic_rational.hpp"
#include "other/mex.hpp"

struct Number_And_Star {
  using A = Dyadic_Rational<ll>;
  // a + *b
  A a;
  int b;
  using T = Number_And_Star;

  Number_And_Star(A a = 0, ll b = 0) : a(a), b(b) {}
  T& operator+=(const T& p) {
    a += p.a, b ^= p.b;
    return *this;
  }
  T& operator-=(const T& p) {
    a -= p.a, b ^= p.b;
    return *this;
  }
  T operator-() const { return T(-a, b); }
  bool operator==(const T& p) const { return (a == p.a && b == p.b); }

  // {計算できたか, 値}
  static pair<bool, T> from_options(vc<T> left_ops, vc<T> right_ops) {
    A xl = -A::infinity(), xr = A::infinity();
    vc<int> Lb, Rb;
    for (auto&& t: left_ops) {
      if (chmax(xl, t.a)) Lb.clear();
      if (xl == t.a) Lb.eb(t.b);
    }
    for (auto&& t: right_ops) {
      if (chmin(xr, t.a)) Rb.clear();
      if (xr == t.a) Rb.eb(t.b);
    }
    int Lm = mex(Lb), Rm = mex(Rb);
    if (xl < xr) {
      A a = A::simplest(xl, xr, Lm == 0, Rm == 0);
      return {true, T(a, 0)};
    }
    if (xl == xr) {
      if (Lm == Rm) return {true, T(xl, Lm)};
    }
    return {false, T(0, 0)};
  }

  string to_string() {
    string x = a.to_string();
    x += " + *";
    x += ::to_string(b);
    return x;
  }

  // L, R はそれぞれ自分手番のときに勝てるか？
  pair<bool, bool> outcome() {
    if (a > 0) return {1, 0};
    if (a < 0) return {0, 1};
    if (b == 0) return {0, 0};
    return {1, 1};
  }
};
#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(X x, X y, bool include_x = false, bool include_y = false) {
    if (include_x && x != -infinity()) {
      // eps を引く, あとでもっと小さい eps を使っている !
      x = x - from_ab(0, 2);
    }
    if (include_y && y != infinity()) {
      // eps を足す
      y = y + from_ab(0, 2);
    }
    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 1 "other/mex.hpp"
int mex(const vc<int>& A) {
  int n = len(A);
  vc<bool> aru(n + 1);
  for (auto& x: A)
    if (x < n) aru[x] = 1;
  int mex = 0;
  while (aru[mex]) ++mex;
  return mex;
}
#line 3 "game/number_and_star.hpp"

struct Number_And_Star {
  using A = Dyadic_Rational<ll>;
  // a + *b
  A a;
  int b;
  using T = Number_And_Star;

  Number_And_Star(A a = 0, ll b = 0) : a(a), b(b) {}
  T& operator+=(const T& p) {
    a += p.a, b ^= p.b;
    return *this;
  }
  T& operator-=(const T& p) {
    a -= p.a, b ^= p.b;
    return *this;
  }
  T operator-() const { return T(-a, b); }
  bool operator==(const T& p) const { return (a == p.a && b == p.b); }

  // {計算できたか, 値}
  static pair<bool, T> from_options(vc<T> left_ops, vc<T> right_ops) {
    A xl = -A::infinity(), xr = A::infinity();
    vc<int> Lb, Rb;
    for (auto&& t: left_ops) {
      if (chmax(xl, t.a)) Lb.clear();
      if (xl == t.a) Lb.eb(t.b);
    }
    for (auto&& t: right_ops) {
      if (chmin(xr, t.a)) Rb.clear();
      if (xr == t.a) Rb.eb(t.b);
    }
    int Lm = mex(Lb), Rm = mex(Rb);
    if (xl < xr) {
      A a = A::simplest(xl, xr, Lm == 0, Rm == 0);
      return {true, T(a, 0)};
    }
    if (xl == xr) {
      if (Lm == Rm) return {true, T(xl, Lm)};
    }
    return {false, T(0, 0)};
  }

  string to_string() {
    string x = a.to_string();
    x += " + *";
    x += ::to_string(b);
    return x;
  }

  // L, R はそれぞれ自分手番のときに勝てるか？
  pair<bool, bool> outcome() {
    if (a > 0) return {1, 0};
    if (a < 0) return {0, 1};
    if (b == 0) return {0, 0};
    return {1, 1};
  }
};
Back to top page