Library

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

View the Project on GitHub noshi91/Library

:warning: other/ll_ext.cpp

Code

#include <cassert>
#include <iostream>
#include <limits>

class ll_ext {
public:
  using ll = long long int;

  enum tag_t {
    finite_tag,
    p_inf_tag,
    n_inf_tag,
  };

  // static constexpr bool infinity_same = true;


  ll v;
  tag_t t;

private:
  static constexpr ll ll_min = std::numeric_limits<ll>::min();
  static constexpr ll ll_max = std::numeric_limits<ll>::max();

  static constexpr bool add_overflow_base(const ll a, const ll b, ll *res) {
    if (a >= 0) {
      if (b >= 0) {
        if (a > ll_max - b) {
          return true;
        }
      }
    } else {
      if (b < 0) {
        if (a < ll_min - b) {
          return true;
        }
      }
    }
    *res = a + b;
    return false;
  }

  static constexpr bool add_overflow(const ll a, const ll b, ll *res) {
#ifdef __GNUC__
    return __builtin_saddll_overflow(a, b, res);
#else
    return add_overflow_base(a, b, res);
#endif
  }

  static constexpr bool sub_overflow_base(const ll a, const ll b, ll *res) {
    if (a >= 0) {
      if (b < 0) {
        if (a > ll_max + b) {
          return true;
        }
      }
    } else {
      if (b >= 0) {
        if (a < ll_min + b) {
          return true;
        }
      }
    }
    *res = a - b;
    return false;
  }

  static constexpr bool sub_overflow(const ll a, const ll b, ll *res) {
#ifdef __GNUC__
    return __builtin_ssubll_overflow(a, b, res);
#else
    return sub_overflow_base(a, b, res);
#endif
  }

  static constexpr bool mul_overflow_base(const ll a, const ll b, ll *res) {
    if (a > 0) {
      if (b > 0) {
        if (a > ll_max / b) {
          return true;
        }
      } else if (b < 0) {
        if (b < ll_min / a) {
          return true;
        }
      }
    } else if (a < 0) {
      if (b > 0) {
        if (a < ll_min / b) {
          return true;
        }
      } else if (b < 0) {
        if (a < ll_max / b) {
          return true;
        }
      }
    }
    *res = a * b;
    return false;
  }

  static constexpr bool mul_overflow(const ll a, const ll b, ll *res) {
#ifdef __GNUC__
    return __builtin_smulll_overflow(a, b, res);
#else
    return mul_overflow_base(a, b, res);
#endif
  }

public:
  static constexpr ll_ext p_infinity() {
    ll_ext ret;
    ret.t = p_inf_tag;
    return ret;
  }
  static constexpr ll_ext n_infinity() {
    ll_ext ret;
    ret.t = n_inf_tag;
    return ret;
  }

  constexpr ll_ext() noexcept : v(0), t(finite_tag) {}
  constexpr ll_ext(const ll x) noexcept : v(x), t(finite_tag) {}

  friend constexpr ll_ext operator+(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        ll x = 0;
        assert(!add_overflow(l.v, r.v, &x) && "overflow: +");
        return x;
      } break;
      case p_inf_tag: {
        return p_infinity();
      } break;
      case n_inf_tag: {
        return n_infinity();
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return p_infinity();
      } break;
      case p_inf_tag: {
        return p_infinity();
      } break;
      case n_inf_tag: {
        assert(false && "p_inf + n_inf");
        return 0;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return n_infinity();
      } break;
      case p_inf_tag: {
        assert(false && "n_inf + p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        return n_infinity();
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator-(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        ll x = 0;
        assert(!sub_overflow(l.v, r.v, &x) && "overflow: -");
        return x;
      } break;
      case p_inf_tag: {
        return n_infinity();
      } break;
      case n_inf_tag: {
        return p_infinity();
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return p_infinity();
      } break;
      case p_inf_tag: {
        assert(false && "p_inf - p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        return p_infinity();
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return n_infinity();
      } break;
      case p_inf_tag: {
        return n_infinity();
      } break;
      case n_inf_tag: {
        assert(false && "n_inf - n_inf");
        return 0;
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator*(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        ll x = 0;
        assert(!mul_overflow(l.v, r.v, &x) && "overflow: *");
        return x;
      } break;
      case p_inf_tag: {
        if (l.v > 0) {
          return p_infinity();
        } else if (l.v == 0) {
          return 0;
        } else {
          return n_infinity();
        }
      } break;
      case n_inf_tag: {
        if (l.v > 0) {
          return n_infinity();
        } else if (l.v == 0) {
          return 0;
        } else {
          return p_infinity();
        }
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return p_infinity();
        } else if (r.v == 0) {
          return 0;
        } else {
          return n_infinity();
        }
      } break;
      case p_inf_tag: {
        return p_infinity();
      } break;
      case n_inf_tag: {
        return n_infinity();
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return n_infinity();
        } else if (r.v == 0) {
          return 0;
        } else {
          return p_infinity();
        }
      } break;
      case p_inf_tag: {
        return n_infinity();
      } break;
      case n_inf_tag: {
        return p_infinity();
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator/(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(r.v != 0 && "division by zero: /");
        assert(!(l.v == ll_min && r.v == -1) && "overflow: /");
        return l.v / r.v;
      } break;
      case p_inf_tag: {
        return 0;
      } break;
      case n_inf_tag: {
        return 0;
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return p_infinity();
        } else if (r.v == 0) {
          assert(false && "division by zero: /");
        } else {
          return n_infinity();
        }
      } break;
      case p_inf_tag: {
        assert(false && "p_inf / p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "p_inf / n_inf");
        return 0;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return n_infinity();
        } else if (r.v == 0) {
          assert(false && "division by zero: /");
        } else {
          return p_infinity();
        }
      } break;
      case p_inf_tag: {
        assert(false && "n_inf / p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "n_inf / n_inf");
        return 0;
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator%(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(r.v != 0 && "division by zero: %");
        assert(!(l.v == ll_min && r.v == -1) && "overflow: %");
        return l.v % r.v;
      } break;
      case p_inf_tag: {
        return l.v;
      } break;
      case n_inf_tag: {
        return l.v;
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(false && "p_inf % finite");
        return 0;
      } break;
      case p_inf_tag: {
        assert(false && "p_inf % p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "p_inf % n_inf");
        return 0;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(false && "n_inf % finite");
        return 0;
      } break;
      case p_inf_tag: {
        assert(false && "n_inf % p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "n_inf % n_inf");
        return 0;
      } break;
      }
    }
    }
  }

  constexpr ll_ext operator+() const noexcept { return *this; }

  constexpr ll_ext operator-() const noexcept {
    switch (t) {
    case finite_tag: {
      assert(v != ll_min && "overflow: unary -");
      return -v;
    } break;
    case p_inf_tag: {
      return n_infinity();
    } break;
    case n_inf_tag: {
      return p_infinity();
    } break;
    }
  }

  constexpr ll_ext &operator+=(const ll_ext &r) noexcept {
    return *this = *this + r;
  }

  constexpr ll_ext &operator-=(const ll_ext &r) noexcept {
    return *this = *this - r;
  }

  constexpr ll_ext &operator*=(const ll_ext &r) noexcept {
    return *this = *this * r;
  }

  constexpr ll_ext &operator/=(const ll_ext &r) noexcept {
    return *this = *this / r;
  }

  constexpr ll_ext &operator%=(const ll_ext &r) noexcept {
    return *this = *this % r;
  }

  friend constexpr bool operator==(const ll_ext &l, const ll_ext &r) noexcept {
    return l.v == r.v && l.t == r.t;
  }

  friend constexpr bool operator!=(const ll_ext &l, const ll_ext &r) noexcept {
    return !(l == r);
  }

  friend constexpr bool operator<(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        return l.v < r.v;
      } break;
      case p_inf_tag: {
        return true;
      } break;
      case n_inf_tag: {
        return false;
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return false;
      } break;
      case p_inf_tag: {
        // assert(false && "p_inf < p_inf");

        return false;
      } break;
      case n_inf_tag: {
        return false;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return true;
      } break;
      case p_inf_tag: {
        return true;
      } break;
      case n_inf_tag: {
        // assert(false && "n_inf < n_inf");

        return false;
      } break;
      }
    }
    }
  }

  friend constexpr bool operator<=(const ll_ext &l, const ll_ext &r) noexcept {
    return !(r < l);
  }

  friend constexpr bool operator>(const ll_ext &l, const ll_ext &r) noexcept {
    return r < l;
  }

  friend constexpr bool operator>=(const ll_ext &l, const ll_ext &r) noexcept {
    return !(l < r);
  }

  friend std::istream &operator>>(std::istream &is, ll_ext &x) {
    x.t = finite_tag;
    is >> x.v;
    return is;
  }

  friend std::ostream &operator<<(std::ostream &os, const ll_ext &x) {
    switch (x.t) {
    case finite_tag: {
      os << x.v;
      return os;
    } break;
    case p_inf_tag: {
      assert(false && "ostream << p_inf");
      return os;
    } break;
    case n_inf_tag: {
      assert(false && "ostream << n_inf");
      return os;
    } break;
    }
  }
};
#line 1 "other/ll_ext.cpp"
#include <cassert>
#include <iostream>
#include <limits>

class ll_ext {
public:
  using ll = long long int;

  enum tag_t {
    finite_tag,
    p_inf_tag,
    n_inf_tag,
  };

  // static constexpr bool infinity_same = true;


  ll v;
  tag_t t;

private:
  static constexpr ll ll_min = std::numeric_limits<ll>::min();
  static constexpr ll ll_max = std::numeric_limits<ll>::max();

  static constexpr bool add_overflow_base(const ll a, const ll b, ll *res) {
    if (a >= 0) {
      if (b >= 0) {
        if (a > ll_max - b) {
          return true;
        }
      }
    } else {
      if (b < 0) {
        if (a < ll_min - b) {
          return true;
        }
      }
    }
    *res = a + b;
    return false;
  }

  static constexpr bool add_overflow(const ll a, const ll b, ll *res) {
#ifdef __GNUC__
    return __builtin_saddll_overflow(a, b, res);
#else
    return add_overflow_base(a, b, res);
#endif
  }

  static constexpr bool sub_overflow_base(const ll a, const ll b, ll *res) {
    if (a >= 0) {
      if (b < 0) {
        if (a > ll_max + b) {
          return true;
        }
      }
    } else {
      if (b >= 0) {
        if (a < ll_min + b) {
          return true;
        }
      }
    }
    *res = a - b;
    return false;
  }

  static constexpr bool sub_overflow(const ll a, const ll b, ll *res) {
#ifdef __GNUC__
    return __builtin_ssubll_overflow(a, b, res);
#else
    return sub_overflow_base(a, b, res);
#endif
  }

  static constexpr bool mul_overflow_base(const ll a, const ll b, ll *res) {
    if (a > 0) {
      if (b > 0) {
        if (a > ll_max / b) {
          return true;
        }
      } else if (b < 0) {
        if (b < ll_min / a) {
          return true;
        }
      }
    } else if (a < 0) {
      if (b > 0) {
        if (a < ll_min / b) {
          return true;
        }
      } else if (b < 0) {
        if (a < ll_max / b) {
          return true;
        }
      }
    }
    *res = a * b;
    return false;
  }

  static constexpr bool mul_overflow(const ll a, const ll b, ll *res) {
#ifdef __GNUC__
    return __builtin_smulll_overflow(a, b, res);
#else
    return mul_overflow_base(a, b, res);
#endif
  }

public:
  static constexpr ll_ext p_infinity() {
    ll_ext ret;
    ret.t = p_inf_tag;
    return ret;
  }
  static constexpr ll_ext n_infinity() {
    ll_ext ret;
    ret.t = n_inf_tag;
    return ret;
  }

  constexpr ll_ext() noexcept : v(0), t(finite_tag) {}
  constexpr ll_ext(const ll x) noexcept : v(x), t(finite_tag) {}

  friend constexpr ll_ext operator+(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        ll x = 0;
        assert(!add_overflow(l.v, r.v, &x) && "overflow: +");
        return x;
      } break;
      case p_inf_tag: {
        return p_infinity();
      } break;
      case n_inf_tag: {
        return n_infinity();
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return p_infinity();
      } break;
      case p_inf_tag: {
        return p_infinity();
      } break;
      case n_inf_tag: {
        assert(false && "p_inf + n_inf");
        return 0;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return n_infinity();
      } break;
      case p_inf_tag: {
        assert(false && "n_inf + p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        return n_infinity();
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator-(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        ll x = 0;
        assert(!sub_overflow(l.v, r.v, &x) && "overflow: -");
        return x;
      } break;
      case p_inf_tag: {
        return n_infinity();
      } break;
      case n_inf_tag: {
        return p_infinity();
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return p_infinity();
      } break;
      case p_inf_tag: {
        assert(false && "p_inf - p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        return p_infinity();
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return n_infinity();
      } break;
      case p_inf_tag: {
        return n_infinity();
      } break;
      case n_inf_tag: {
        assert(false && "n_inf - n_inf");
        return 0;
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator*(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        ll x = 0;
        assert(!mul_overflow(l.v, r.v, &x) && "overflow: *");
        return x;
      } break;
      case p_inf_tag: {
        if (l.v > 0) {
          return p_infinity();
        } else if (l.v == 0) {
          return 0;
        } else {
          return n_infinity();
        }
      } break;
      case n_inf_tag: {
        if (l.v > 0) {
          return n_infinity();
        } else if (l.v == 0) {
          return 0;
        } else {
          return p_infinity();
        }
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return p_infinity();
        } else if (r.v == 0) {
          return 0;
        } else {
          return n_infinity();
        }
      } break;
      case p_inf_tag: {
        return p_infinity();
      } break;
      case n_inf_tag: {
        return n_infinity();
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return n_infinity();
        } else if (r.v == 0) {
          return 0;
        } else {
          return p_infinity();
        }
      } break;
      case p_inf_tag: {
        return n_infinity();
      } break;
      case n_inf_tag: {
        return p_infinity();
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator/(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(r.v != 0 && "division by zero: /");
        assert(!(l.v == ll_min && r.v == -1) && "overflow: /");
        return l.v / r.v;
      } break;
      case p_inf_tag: {
        return 0;
      } break;
      case n_inf_tag: {
        return 0;
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return p_infinity();
        } else if (r.v == 0) {
          assert(false && "division by zero: /");
        } else {
          return n_infinity();
        }
      } break;
      case p_inf_tag: {
        assert(false && "p_inf / p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "p_inf / n_inf");
        return 0;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        if (r.v > 0) {
          return n_infinity();
        } else if (r.v == 0) {
          assert(false && "division by zero: /");
        } else {
          return p_infinity();
        }
      } break;
      case p_inf_tag: {
        assert(false && "n_inf / p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "n_inf / n_inf");
        return 0;
      } break;
      }
    }
    }
  }

  friend constexpr ll_ext operator%(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(r.v != 0 && "division by zero: %");
        assert(!(l.v == ll_min && r.v == -1) && "overflow: %");
        return l.v % r.v;
      } break;
      case p_inf_tag: {
        return l.v;
      } break;
      case n_inf_tag: {
        return l.v;
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(false && "p_inf % finite");
        return 0;
      } break;
      case p_inf_tag: {
        assert(false && "p_inf % p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "p_inf % n_inf");
        return 0;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        assert(false && "n_inf % finite");
        return 0;
      } break;
      case p_inf_tag: {
        assert(false && "n_inf % p_inf");
        return 0;
      } break;
      case n_inf_tag: {
        assert(false && "n_inf % n_inf");
        return 0;
      } break;
      }
    }
    }
  }

  constexpr ll_ext operator+() const noexcept { return *this; }

  constexpr ll_ext operator-() const noexcept {
    switch (t) {
    case finite_tag: {
      assert(v != ll_min && "overflow: unary -");
      return -v;
    } break;
    case p_inf_tag: {
      return n_infinity();
    } break;
    case n_inf_tag: {
      return p_infinity();
    } break;
    }
  }

  constexpr ll_ext &operator+=(const ll_ext &r) noexcept {
    return *this = *this + r;
  }

  constexpr ll_ext &operator-=(const ll_ext &r) noexcept {
    return *this = *this - r;
  }

  constexpr ll_ext &operator*=(const ll_ext &r) noexcept {
    return *this = *this * r;
  }

  constexpr ll_ext &operator/=(const ll_ext &r) noexcept {
    return *this = *this / r;
  }

  constexpr ll_ext &operator%=(const ll_ext &r) noexcept {
    return *this = *this % r;
  }

  friend constexpr bool operator==(const ll_ext &l, const ll_ext &r) noexcept {
    return l.v == r.v && l.t == r.t;
  }

  friend constexpr bool operator!=(const ll_ext &l, const ll_ext &r) noexcept {
    return !(l == r);
  }

  friend constexpr bool operator<(const ll_ext &l, const ll_ext &r) noexcept {
    switch (l.t) {
    case finite_tag: {
      switch (r.t) {
      case finite_tag: {
        return l.v < r.v;
      } break;
      case p_inf_tag: {
        return true;
      } break;
      case n_inf_tag: {
        return false;
      } break;
      }
    } break;
    case p_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return false;
      } break;
      case p_inf_tag: {
        // assert(false && "p_inf < p_inf");

        return false;
      } break;
      case n_inf_tag: {
        return false;
      } break;
      }
    } break;
    case n_inf_tag: {
      switch (r.t) {
      case finite_tag: {
        return true;
      } break;
      case p_inf_tag: {
        return true;
      } break;
      case n_inf_tag: {
        // assert(false && "n_inf < n_inf");

        return false;
      } break;
      }
    }
    }
  }

  friend constexpr bool operator<=(const ll_ext &l, const ll_ext &r) noexcept {
    return !(r < l);
  }

  friend constexpr bool operator>(const ll_ext &l, const ll_ext &r) noexcept {
    return r < l;
  }

  friend constexpr bool operator>=(const ll_ext &l, const ll_ext &r) noexcept {
    return !(l < r);
  }

  friend std::istream &operator>>(std::istream &is, ll_ext &x) {
    x.t = finite_tag;
    is >> x.v;
    return is;
  }

  friend std::ostream &operator<<(std::ostream &os, const ll_ext &x) {
    switch (x.t) {
    case finite_tag: {
      os << x.v;
      return os;
    } break;
    case p_inf_tag: {
      assert(false && "ostream << p_inf");
      return os;
    } break;
    case n_inf_tag: {
      assert(false && "ostream << n_inf");
      return os;
    } break;
    }
  }
};
Back to top page