tests/rational_binary_search.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://judge.yosupo.jp/problem/rational_approximation

Depends on

• Rational binary search (tools/rational_binary_search.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/rational_approximation

#include <iostream>
#include <tuple>
#include <utility>
#include "tools/rational_binary_search.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int T;
  std::cin >> T;
  for (int t = 0; t < T; ++t) {
    ll N, x, y;
    std::cin >> N >> x >> y;
    if (x < y) {
      auto [p1, q1, p2, q2] = tools::rational_binary_search(0LL, 1LL, 1LL, 0LL, [&](const auto& p, const auto& q) { return p * y <= x * q; }, N);
      if (p1 * y == x * q1) std::tie(p2, q2) = std::make_pair(p1, q1);
      std::cout << p1 << ' ' << q1 << ' ' << p2 << ' ' << q2 << '\n';
    } else {
      auto [q2, p2, q1, p1] = tools::rational_binary_search(0LL, 1LL, 1LL, 0LL, [&](const auto& q, const auto& p) { return q * x <= y * p; }, N);
      if (q2 * x == y * p2) std::tie(p1, q1) = std::make_pair(p2, q2);
      std::cout << p1 << ' ' << q1 << ' ' << p2 << ' ' << q2 << '\n';
    }
  }

  return 0;
}

#line 1 "tests/rational_binary_search.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/rational_approximation

#include <iostream>
#include <tuple>
#include <utility>
#line 1 "tools/rational_binary_search.hpp"



#line 5 "tools/rational_binary_search.hpp"
#include <cassert>

namespace tools {
  template <typename T, typename F>
  ::std::tuple<T, T, T, T> rational_binary_search(const T& p1, const T& q1, const T& p2, const T& q2, const F& f, const T& N) {
    assert(q1 >= T(0));
    assert(q2 >= T(0));
    assert(N > T(0));
    assert(p1 * q2 < p2 * q1);
    const bool f1 = f(p1, q1);
    const bool f2 = f(p2, q2);
    assert(f1 != f2);
    const auto g = [&](const T& p, const T& q) {
      assert(q > T(0));
      if (p * q1 < p1 * q) return f1;
      if (p2 * q < p * q2) return f2;
      return f(p, q);
    };

    bool d = g(T(0), T(1)) == f1;
    T p3, q3, p4, q4;
    if (d) {
      p3 = T(0);
      q3 = T(1);
      p4 = T(1);
      q4 = T(0);
    } else {
      p3 = T(-1);
      q3 = T(0);
      p4 = T(0);
      q4 = T(1);
    }

    while (q3 <= N - q4) {
      if (d) {
        T ng(1);
        if (q4 == T(0)) {
          for (; g(p3 + ng * p4, q3) == f1; ng *= T(2));
        } else {
          const T max = (N - q3) / q4;
          for (; ng <= max && g(p3 + ng * p4, q3 + ng * q4) == f1; ng = (ng == max ? ng + T(1) : ng <= max / T(2) ? T(2) * ng : max));
          if (ng == max + T(1)) {
            --ng;
            p3 += ng * p4;
            q3 += ng * q4;
            break;
          }
        }
        T ok(0);
        while (ng - ok > T(1)) {
          const auto mid = ok + (ng - ok) / T(2);
          if (g(p3 + mid * p4, q3 + mid * q4) == f1) {
            ok = mid;
          } else {
            ng = mid;
          }
        }
        ::std::tie(p3, q3, p4, q4) = ::std::make_tuple(p3 + ok * p4, q3 + ok * q4, p3 + ng * p4, q3 + ng * q4);
      } else {
        T ng(1);
        if (q3 == T(0)) {
          for (; g(ng * p3 + p4, q4) == f2; ng *= T(2));
        } else {
          const T max = (N - q4) / q3;
          for (; ng <= max && g(ng * p3 + p4, ng * q3 + q4) == f2; ng = (ng == max ? ng + T(1) : ng <= max / T(2) ? T(2) * ng : max));
          if (ng == max + T(1)) {
            --ng;
            p4 += ng * p3;
            q4 += ng * q3;
            break;
          }
        }
        T ok(0);
        while (ng - ok > T(1)) {
          const auto mid = ok + (ng - ok) / T(2);
          if (g(mid * p3 + p4, mid * q3 + q4) == f2) {
            ok = mid;
          } else {
            ng = mid;
          }
        }
        ::std::tie(p3, q3, p4, q4) = ::std::make_tuple(ng * p3 + p4, ng * q3 + q4, ok * p3 + p4, ok * q3 + q4);
      }
      d = !d;
    }

    return ::std::make_tuple(p3, q3, p4, q4);
  }
}


#line 7 "tests/rational_binary_search.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int T;
  std::cin >> T;
  for (int t = 0; t < T; ++t) {
    ll N, x, y;
    std::cin >> N >> x >> y;
    if (x < y) {
      auto [p1, q1, p2, q2] = tools::rational_binary_search(0LL, 1LL, 1LL, 0LL, [&](const auto& p, const auto& q) { return p * y <= x * q; }, N);
      if (p1 * y == x * q1) std::tie(p2, q2) = std::make_pair(p1, q1);
      std::cout << p1 << ' ' << q1 << ' ' << p2 << ' ' << q2 << '\n';
    } else {
      auto [q2, p2, q1, p1] = tools::rational_binary_search(0LL, 1LL, 1LL, 0LL, [&](const auto& q, const auto& p) { return q * x <= y * p; }, N);
      if (q2 * x == y * p2) std::tie(p1, q1) = std::make_pair(p2, q2);
      std::cout << p1 << ' ' << q1 << ' ' << p2 << ' ' << q2 << '\n';
    }
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	boundary_00	AC	5 ms	4 MB
g++	example_00	AC	4 ms	4 MB
g++	fibonacci_00	AC	60 ms	4 MB
g++	input_reducible_00	AC	78 ms	4 MB
g++	large_run_length_00	AC	54 ms	4 MB
g++	random_00	AC	18 ms	4 MB
g++	random_01	AC	59 ms	4 MB
g++	random_02	AC	46 ms	4 MB
g++	random_large_00	AC	79 ms	4 MB
g++	random_large_01	AC	80 ms	4 MB
g++	random_large_02	AC	80 ms	4 MB
g++	small_all_00	AC	31 ms	4 MB
g++	small_all_01	AC	34 ms	4 MB
g++	small_all_02	AC	36 ms	4 MB
g++	small_all_03	AC	37 ms	4 MB
g++	small_all_04	AC	37 ms	4 MB
g++	small_all_05	AC	39 ms	4 MB
g++	small_all_06	AC	39 ms	4 MB
g++	small_all_07	AC	40 ms	4 MB
g++	small_all_08	AC	40 ms	4 MB
g++	small_all_09	AC	40 ms	4 MB
g++	small_run_length_00	AC	62 ms	4 MB
g++	small_run_length_01	AC	74 ms	4 MB
g++	small_run_length_02	AC	77 ms	4 MB
g++	small_run_length_03	AC	71 ms	4 MB
g++	small_run_length_04	AC	71 ms	4 MB
g++	trivial_00	AC	81 ms	4 MB
g++	zero_or_inf_00	AC	35 ms	4 MB

Back to top page