cp-documentation

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

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/AtCoder/abc333_g.test.cpp

Depends on

Code

// #define PROBLEM "https://atcoder.jp/contests/abc333/tasks/abc333_g"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/Utility/FloatingMarkerShift.hpp"
#include "../../Src/Utility/RationalBinarySearch.hpp"

#include <iostream>
#include <string>
#include <numeric>

using namespace zawa;
using namespace std;

__int128_t my_abs(__int128_t v) {
    return v < 0 ? -v : v;
}

int main() {
#ifdef ATCODER
    string rs;
    long long n;
    cin >> rs >> n;
    long long num = FloatingMarkerShift(rs, 18), den = 1000000000000000000LL;
    long long g = gcd(num, den);
    num /= g;
    den /= g;
    auto f = [&](long long x, long long y) -> bool {
        return (__int128_t)x * den <= (__int128_t)num * y;
    };
    auto [max_ok, min_ng] = RationalBinarySearch(f, n);
    auto [a, b] = max_ok;
    auto [c, d] = min_ng;
    if ((long double)2 * num * d * b > ((long double)c * b + (long double)a * d) * den) {
        swap(a, c);
        swap(b, d);
    }
    cout << a << ' ' << b << '\n';
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/AtCoder/abc333_g.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc333/tasks/abc333_g"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Utility/FloatingMarkerShift.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Utility/FloatingMarkerShift.hpp"

#include <string>
#include <cassert>
#include <limits>

namespace zawa {

i64 FloatingMarkerShift(const std::string& S, u32 shift) {
    static i64 lim10{std::numeric_limits<i64>::max() / 10};
    assert(not S.empty());
    i64 res{};
    u32 moved{};
    bool start{};
    bool minus{S[0] == '-'};
    for (u32 i{(u32)minus} ; i < S.size() ; i++) {
        if (S[i] == '.') {
            start = true;
        }
        else {
            if (start) moved++;
            assert(res < lim10);
            res = res * 10;
            assert(res < std::numeric_limits<i64>::max() - (S[i] - '0'));
            res += S[i] - '0';
        }
    }
    assert(moved <= shift);
    while (moved < shift) {
        moved++;
        assert(res < lim10);
        res = res * 10;
    }
    if (minus) res *= -1;
    return res;
}

}// namespace zawa
#line 2 "Src/Utility/RationalBinarySearch.hpp"

#line 4 "Src/Utility/RationalBinarySearch.hpp"
#include <concepts>
#include <utility>

namespace zawa {

template <class F, std::integral T>
requires std::predicate<F, T, T>
std::pair<std::pair<T, T>, std::pair<T, T>> RationalBinarySearch(F f, T n) {
    assert(f(0, 1) and !f(1, 0));
    auto dfs = [&](auto dfs, bool cur, T& p, T& q, T pp, T pq) -> void {
        if (p + pp > n or q + pq > n) return;
        if (f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
            dfs(dfs, cur, p, q, pp << 1, pq << 1);
        }
        if (p + pp <= n and q + pq <= n and f(p + pp, q + pq) == cur) {
            p += pp;
            q += pq;
        }
    };
    T pl = 0, ql = 1, pr = 1, qr = 0;
    while (pl + pr <= n and ql + qr <= n) {
        dfs(dfs, true, pl, ql, pr, qr);
        dfs(dfs, false, pr, qr, pl, ql);
    }
    return std::pair{std::pair{pl, ql}, std::pair{pr, qr}};
}

} // namespace zawa
#line 6 "Test/AtCoder/abc333_g.test.cpp"

#include <iostream>
#line 9 "Test/AtCoder/abc333_g.test.cpp"
#include <numeric>

using namespace zawa;
using namespace std;

__int128_t my_abs(__int128_t v) {
    return v < 0 ? -v : v;
}

int main() {
#ifdef ATCODER
    string rs;
    long long n;
    cin >> rs >> n;
    long long num = FloatingMarkerShift(rs, 18), den = 1000000000000000000LL;
    long long g = gcd(num, den);
    num /= g;
    den /= g;
    auto f = [&](long long x, long long y) -> bool {
        return (__int128_t)x * den <= (__int128_t)num * y;
    };
    auto [max_ok, min_ng] = RationalBinarySearch(f, n);
    auto [a, b] = max_ok;
    auto [c, d] = min_ng;
    if ((long double)2 * num * d * b > ((long double)c * b + (long double)a * d) * den) {
        swap(a, c);
        swap(b, d);
    }
    cout << a << ' ' << b << '\n';
#else
    cout << "Hello World\n";
#endif
}
Back to top page