#760661 (C++17) No.1936 Rational Approximation

• 問題: No.1936 Rational Approximation
• ユーザー: r1933
• 提出日時: 2022-05-13 22:23:35
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE
• 実行時間: -
• コード長: 8,163 bytes
• コンパイル時間: 2,388 ms
• コンパイル使用メモリ: 205,136 KB
• 実行使用メモリ: 16,952 KB
• 最終ジャッジ日時: 2024-07-22 02:25:21
• 合計ジャッジ時間: 8,790 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	TLE	-
testcase_01	--	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-

ソースコード

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

// Begin Header {{{
#pragma region
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i)
#define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i)
#define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i)
#define var(Type, ...) \
    Type __VA_ARGS__;  \
    input(__VA_ARGS__)
#define let const auto

constexpr size_t operator""_zu(unsigned long long value) {
    return value;
};
constexpr intmax_t operator""_jd(unsigned long long value) {
    return value;
};
constexpr uintmax_t operator""_ju(unsigned long long value) {
    return value;
};

constexpr int INF = 0x3f3f3f3f;
constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd;

using usize = size_t;
using imax = intmax_t;
using uimax = uintmax_t;
using ld = long double;

template <class T, class Compare = less<>>
using MaxHeap = priority_queue<T, vector<T>, Compare>;
template <class T, class Compare = greater<>>
using MinHeap = priority_queue<T, vector<T>, Compare>;

inline void input() {}
template <class Head, class... Tail>
inline void input(Head&& head, Tail&&... tail) {
    cin >> head;
    input(forward<Tail>(tail)...);
}

template <class Container, class Value = typename Container::value_type,
          enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr>
inline istream& operator>>(istream& is, Container& vs) {
    for (auto& v: vs) is >> v;
    return is;
}

template <class T, class U>
inline istream& operator>>(istream& is, pair<T, U>& p) {
    is >> p.first >> p.second;
    return is;
}

inline void output() {
    cout << "\n";
}
template <class Head, class... Tail>
inline void output(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << " ";
    output(forward<Tail>(tail)...);
}

template <class Container, class Value = typename Container::value_type,
          enable_if_t<!is_same<Container, string>::value, nullptr_t> = nullptr>
inline ostream& operator<<(ostream& os, const Container& vs) {
    static constexpr const char* delim[] = {" ", ""};
    for (auto it = begin(vs); it != end(vs); ++it) {
        os << delim[it == begin(vs)] << *it;
    }
    return os;
}

template <class Iterator>
inline void join(const Iterator& Begin, const Iterator& End, const string& delim = "\n",
                 const string& last = "\n") {
    for (auto it = Begin; it != End; ++it) {
        cout << ((it == Begin) ? "" : delim) << *it;
    }
    cout << last;
}

template <class T>
inline vector<T> makeVector(const T& init_value, size_t sz) {
    return vector<T>(sz, init_value);
}

template <class T, class... Args>
inline auto makeVector(const T& init_value, size_t sz, Args... args) {
    return vector<decltype(makeVector<T>(init_value, args...))>(
        sz, makeVector<T>(init_value, args...));
}

template <class Func>
class FixPoint : Func {
public:
    explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}

    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return Func::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
    return FixPoint<Func> {forward<Func>(f)};
}

template <class Container>
struct reverse_t {
    Container& c;
    reverse_t(Container& c) : c(c) {}
    auto begin() {
        return c.rbegin();
    }
    auto end() {
        return c.rend();
    }
};

template <class Container>
auto reversed(Container& c) {
    return reverse_t<Container>(c);
}

template <class T>
inline bool chmax(T& a, const T& b) noexcept {
    return b > a && (a = b, true);
}

template <class T>
inline bool chmin(T& a, const T& b) noexcept {
    return b < a && (a = b, true);
}

template <class T>
inline T diff(const T& a, const T& b) noexcept {
    return a < b ? b - a : a - b;
}

void operator|=(vector<bool>::reference lhs, const bool rhs) {
    lhs = lhs | rhs;
}

void operator&=(vector<bool>::reference lhs, const bool rhs) {
    lhs = lhs & rhs;
}

void operator^=(vector<bool>::reference lhs, const bool rhs) {
    lhs = lhs ^ rhs;
}

void ioinit() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
    clog << fixed << setprecision(10);
}
#pragma endregion
// }}} End Header

// Fraction {{{
class Fraction {
private:
    constexpr static inline intmax_t gcd(intmax_t a, intmax_t b) {
        return b == 0 ? abs(a) : gcd(b, a % b);
    }

public:
    intmax_t numer, denom;

    Fraction() {
        numer = 0;
        denom = 1;
    }
    Fraction(intmax_t n, intmax_t d) {
        if (n == 0) {
            numer = 0;
            denom = 1;
        } else {
            int sign = ((n < 0) == (d < 0) ? 1 : -1);
            n = abs(n), d = abs(d);

            intmax_t g = gcd(n, d);
            numer = sign * n / g;
            denom = d / g;
        }
    }

    template <typename T>
    constexpr explicit operator T() const {
        return static_cast<T>(numer) / denom;
    }
};

Fraction operator+(const Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.denom + rhs.numer * lhs.denom, lhs.denom * rhs.denom);
    return ret;
}
Fraction operator+=(Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.denom + rhs.numer * lhs.denom, lhs.denom * rhs.denom);
    lhs = ret;
    return lhs;
}
Fraction operator-(const Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.denom - rhs.numer * lhs.denom, lhs.denom * rhs.denom);
    return ret;
}
Fraction operator-=(Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.denom - rhs.numer * lhs.denom, lhs.denom * rhs.denom);
    lhs = ret;
    return lhs;
}
Fraction operator*(const Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.numer, lhs.denom * rhs.denom);
    return ret;
}
Fraction operator*=(Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.numer, lhs.denom * rhs.denom);
    lhs = ret;
    return lhs;
}
Fraction operator/(const Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.denom, lhs.denom * rhs.numer);
    return ret;
}
Fraction operator/=(Fraction& lhs, const Fraction& rhs) {
    Fraction ret(lhs.numer * rhs.denom, lhs.denom * rhs.numer);
    lhs = ret;
    return lhs;
}

bool operator<(const Fraction& lhs, const Fraction& rhs) {
    const intmax_t lhs_numer = lhs.numer * rhs.denom;
    const intmax_t rhs_numer = rhs.numer * lhs.denom;
    return lhs_numer < rhs_numer;
}
bool operator>(const Fraction& lhs, const Fraction& rhs) {
    return rhs < lhs;
}
bool operator<=(const Fraction& lhs, const Fraction& rhs) {
    return !(lhs > rhs);
}
bool operator>=(const Fraction& lhs, const Fraction& rhs) {
    return !(lhs < rhs);
}
bool operator==(const Fraction& lhs, const Fraction& rhs) {
    return !(lhs < rhs) && !(lhs > rhs);
}
bool operator!=(const Fraction& lhs, const Fraction& rhs) {
    return (lhs < rhs) || (lhs > rhs);
}

istream& operator>>(istream& is, Fraction& f) {
    is >> f.numer >> f.denom;
    return is;
}
ostream& operator<<(ostream& os, const Fraction& f) {
    if (f.denom == 1) {
        os << f.numer;
    } else {
        os << f.numer << '/' << f.denom;
    }
    return os;
}
// }}}

// \\ TLE !!!!!!!!!! //
Fraction L(0, 1), R(1, 0);

void stern_brocot(intmax_t p, intmax_t q) {
    const Fraction mediant(L.numer + R.numer, L.denom + R.denom);
    const intmax_t mn = mediant.numer;
    const intmax_t md = mediant.denom;

    if (md >= q) return;

    if (mn * q < md * p) {
        L = mediant;
        stern_brocot(p, q);
    } else if (md * p < mn * q) {
        R = mediant;
        stern_brocot(p, q);
    } else {
        L = R = mediant;
    }
}

int main() {
    ioinit();
    // もけと和解せよ \\🐈//

    var(intmax_t, P, Q);
    stern_brocot(P, Q);
    output(L.numer + L.denom + R.numer + R.denom);
    return 0;
}