結果
| 問題 |
No.1936 Rational Approximation
|
| ユーザー |
 r1933
|
| 提出日時 | 2022-05-13 22:13:06 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,227 bytes |
| コンパイル時間 | 2,047 ms |
| コンパイル使用メモリ | 198,556 KB |
| 最終ジャッジ日時 | 2025-01-29 07:03:28 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 11 TLE * 3 |
ソースコード
#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;
}
// }}}
Fraction L, R;
void stern_brocot(intmax_t p, intmax_t q, Fraction l = Fraction(0, 1),
Fraction r = Fraction(1, 0)) {
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, mediant, r);
} else if (md * p < mn * q) {
R = mediant;
stern_brocot(p, q, l, mediant);
} 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;
}