Language: C++

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

struct fraction {
    static const bool CHECK_OVERFLOW64 = true;

    static int cross_sign(const fraction &a, const fraction &b) {
        if (CHECK_OVERFLOW64) {
            long double double_value = (long double) a.numer * b.denom - (long double) b.numer * a.denom;

            if (abs(double_value) > 1e18)
                return double_value > 0 ? +1 : -1;
        }

        uint64_t uint64_value = (uint64_t) a.numer * b.denom - (uint64_t) b.numer * a.denom;

        if (uint64_value == 0)
            return 0;

        return uint64_value >> 63 ? -1 : +1;
    }

    long long numer, denom;

    fraction(long long n = 0, long long d = 1) : numer(n), denom(d) {
        reduce();
    }

    void reduce() {
        assert(denom > 0);
        long long g = __gcd(abs(numer), denom);
        numer /= g;
        denom /= g;
    }

    friend fraction operator+(const fraction &a, const fraction &b) {
        return fraction(a.numer * b.denom + b.numer * a.denom, a.denom * b.denom);
    }

    friend fraction operator-(const fraction &a, const fraction &b) {
        return fraction(a.numer * b.denom - b.numer * a.denom, a.denom * b.denom);
    }

    friend fraction operator*(const fraction &a, const fraction &b) {
        return fraction(a.numer * b.numer, a.denom * b.denom);
    }

    friend fraction operator/(const fraction &a, const fraction &b) {
        return fraction(a.numer * b.denom, a.denom * b.numer);
    }

    fraction& operator+=(const fraction &other) { return *this = *this + other; }
    fraction& operator-=(const fraction &other) { return *this = *this - other; }
    fraction& operator*=(const fraction &other) { return *this = *this * other; }
    fraction& operator/=(const fraction &other) { return *this = *this / other; }

    fraction& operator++() { numer += denom; return *this; }
    fraction& operator--() { numer -= denom; return *this; }

    fraction operator++(int) { fraction before = *this; ++*this; return before; }
    fraction operator--(int) { fraction before = *this; --*this; return before; }

    fraction operator-() const {
        return fraction(-numer, denom);
    }

    fraction inv() const {
        return fraction(denom, numer);
    }

    bool operator==(const fraction &other) const { return cross_sign(*this, other) == 0; }
    bool operator!=(const fraction &other) const { return cross_sign(*this, other) != 0; }
    bool operator<(const fraction &other) const { return cross_sign(*this, other) < 0; }
    bool operator>(const fraction &other) const { return cross_sign(*this, other) > 0; }
    bool operator<=(const fraction &other) const { return cross_sign(*this, other) <= 0; }
    bool operator>=(const fraction &other) const { return cross_sign(*this, other) >= 0; }

    double to_double() const {
        return (double) numer / denom;
    }

    friend ostream& operator<<(ostream& out, const fraction &frac) {
        return out << frac.numer << '/' << frac.denom;
    }
};

template<typename T>
struct fenwick_tree {
    int tree_n = 0;
    T tree_sum = 0;
    vector<T> tree;

    fenwick_tree(int n = -1) {
        if (n >= 0)
            init(n);
    }

    void init(int n) {
        tree_n = n;
        tree_sum = 0;
        tree.assign(tree_n + 1, 0);
    }

    // O(n) initialization of the Fenwick tree.
    template<typename T_array>
    void build(const T_array &initial) {
        assert((int) initial.size() == tree_n);
        tree_sum = 0;

        for (int i = 1; i <= tree_n; i++) {
            tree[i] = initial[i - 1];
            tree_sum += initial[i - 1];

            for (int k = (i & -i) >> 1; k > 0; k >>= 1)
                tree[i] += tree[i - k];
        }
    }

    // index is in [0, tree_n).
    void update(int index, const T &change) {
        assert(0 <= index && index < tree_n);
        tree_sum += change;

        for (int i = index + 1; i <= tree_n; i += i & -i)
            tree[i] += change;
    }

    // Returns the sum of the range [0, count).
    T query(int count) const {
        assert(count <= tree_n);
        T sum = 0;

        for (int i = count; i > 0; i -= i & -i)
            sum += tree[i];

        return sum;
    }

    // Returns the sum of the range [start, tree_n).
    T query_suffix(int start) const {
        return tree_sum - query(start);
    }

    // Returns the sum of the range [a, b).
    T query(int a, int b) const {
        return query(b) - query(a);
    }

    // Returns the element at index a in O(1) amortized across every index. Equivalent to query(a, a + 1).
    T get(int a) const {
        assert(0 <= a && a < tree_n);
        int above = a + 1;
        T sum = tree[above];
        above -= above & -above;

        while (a != above) {
            sum -= tree[a];
            a -= a & -a;
        }

        return sum;
    }

    // Returns the last i in [0, N] such that query(i) <= sum, or -1 if no such i exists.
    int find_last_prefix(T sum) const {
        if (sum < 0)
            return -1;

        int prefix = 0;

        for (int k = 31 - __builtin_clz(tree_n); k >= 0; k--)
            if (prefix + (1 << k) <= tree_n && tree[prefix + (1 << k)] <= sum) {
                prefix += 1 << k;
                sum -= tree[prefix];
            }

        return prefix;
    }
};


struct beam {
    int a, b, index;
};

bool compare_a(beam x, beam y) {
    return x.a < y.a;
}

bool compare_b(beam x, beam y) {
    return x.b < y.b;
}

int N;
vector<beam> beams;
fenwick_tree<long long> tree;
fenwick_tree<int> one_tree;

fraction evaluate(long long a_sum) {
    long long b_sum = tree.query(N);

    if (a_sum >= b_sum)
        return {0, 1};

    int prefix = tree.find_last_prefix(b_sum - a_sum);
    assert(prefix < N);
    long long b = tree.get(prefix);
    assert(b > 0);
    long long numer = (long long) one_tree.query(prefix + 1) * b - (a_sum - tree.query_suffix(prefix + 1));
    long long denom = b;
    return {numer, denom};
}

// fraction evaluate(long long a_sum, vector<int> B) {
//     sort(B.begin(), B.end());

//     while (!B.empty() && a_sum >= B.back()) {
//         a_sum -= B.back();
//         B.pop_back();
//     }

//     if (B.empty())
//         return {0, 1};

//     long long numer = (long long) B.size() * B.back() - a_sum;
//     long long denom = B.back();
//     return {numer, denom};
// }

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

    cin >> N;
    beams.resize(N);

    for (beam &bm : beams)
        cin >> bm.a >> bm.b;

    sort(beams.begin(), beams.end(), compare_b);

    for (int i = 0; i < N; i++)
        beams[i].index = i;

    vector<beam> new_beams;
    long long a_sum = 0;
    tree.init(N);
    one_tree.init(N);

    for (int i = 0; i < N; i++)
        if (beams[i].a <= beams[i].b) {
            a_sum += beams[i].a;
            tree.update(i, beams[i].b);
            one_tree.update(i, +1);
        } else {
            new_beams.push_back(beams[i]);
        }

    swap(beams, new_beams);
    new_beams = {};
    sort(beams.begin(), beams.end(), compare_a);
    int prev_index = -1, prev_a = -1, prev_b = -1;
    fraction current = evaluate(a_sum);

    // cerr << "initial: " << evaluate(a_sum).to_double() << endl;

    for (beam &bm : beams) {
        tree.update(bm.index, bm.b);
        one_tree.update(bm.index, +1);
        // cerr << bm.a << ' ' << bm.b << ": " << evaluate(a_sum + bm.a).to_double() << endl;

        if (evaluate(a_sum + bm.a) > current) {
            a_sum += bm.a;
            current = evaluate(a_sum);
            prev_index = bm.index;
            prev_a = bm.a;
            prev_b = bm.b;
            // cerr << "improved: " << evaluate(a_sum).to_double() << endl;
            // cerr << "with " << bm.a << ' ' << bm.b << endl;
        } else if (prev_index >= 0) {
            tree.update(prev_index, -prev_b);
            one_tree.update(prev_index, -1);

            if (evaluate(a_sum + bm.a - prev_a) > current) {
                a_sum += bm.a - prev_a;
                current = evaluate(a_sum);
                prev_index = bm.index;
                prev_a = bm.a;
                prev_b = bm.b;
                // cerr << "replaced: " << evaluate(a_sum).to_double() << endl;
                // cerr << "with " << bm.a << ' ' << bm.b << endl;
            } else {
                tree.update(prev_index, prev_b);
                one_tree.update(prev_index, +1);
                tree.update(bm.index, -bm.b);
                one_tree.update(bm.index, -1);
            }
        } else {
            tree.update(bm.index, -bm.b);
            one_tree.update(bm.index, -1);
        }
    }

    current.denom *= N;
    current.reduce();
    cout << current.numer << ' ' << current.denom << '\n';
}


Compiler output:
a.cc: In static member function 'static int fraction::cross_sign(const fraction&, const fraction&)':
a.cc:18:9: error: 'uint64_t' was not declared in this scope
   18 |         uint64_t uint64_value = (uint64_t) a.numer * b.denom - (uint64_t) b.numer * a.denom;
      |         ^~~~~~~~
a.cc:5:1: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    4 | #include <vector>
  +++ |+#include <cstdint>
    5 | using namespace std;
a.cc:20:13: error: 'uint64_value' was not declared in this scope
   20 |         if (uint64_value == 0)
      |             ^~~~~~~~~~~~
a.cc:23:16: error: 'uint64_value' was not declared in this scope
   23 |         return uint64_value >> 63 ? -1 : +1;
      |                ^~~~~~~~~~~~