Problem:


Score : 1100 points

Problem Statement

We have N balance beams numbered 1 to N.
The length of each beam is 1 meters.
Snuke walks on Beam i at a speed of 1/A_i meters per second, and Ringo walks on Beam i at a speed of 1/B_i meters per second.

Snuke and Ringo will play the following game:

First, Snuke connects the N beams in any order of his choice and makes a long beam of length N meters.

Then, Snuke starts at the left end of the long beam. At the same time, Ringo starts at a point chosen uniformly at random on the long beam. Both of them walk to the right end of the long beam.

Snuke wins if and only if he catches up to Ringo before Ringo reaches the right end of the long beam. That is, Snuke wins if there is a moment when Snuke and Ringo stand at the same position, and Ringo wins otherwise.

Find the probability that Snuke wins when Snuke arranges the N beams so that the probability of his winning is maximized.

This probability is a rational number, so we ask you to represent it as an irreducible fraction P/Q (to represent 0, use P=0, Q=1).

Constraints

1 \leq N \leq 10^5

1 \leq A_i,B_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the numerator and denominator of the irreducible fraction that represents the maximum probability of Snuke's winning.

Sample Input 1

2
3 2
1 2

Sample Output 1

1 4

When the beams are connected in the order 2,1 from left to right, the probability of Snuke's winning is 1/4, which is the maximum possible value.

Sample Input 2

4
1 5
4 7
2 1
8 4

Sample Output 2

1 2

Sample Input 3

3
4 1
5 2
6 3

Sample Output 3

0 1

Sample Input 4

10
866111664 178537096
705445072 318106937
472381277 579910117
353498483 865935868
383133839 231371336
378371075 681212831
304570952 16537461
955719384 267238505
844917655 218662351
550309930 62731178

Sample Output 4

697461712 2899550585



Sample input:
2
3 2
1 2


Sample output:
1 4

Submission status: Wrong Answer

Solution code:
import heapq

class Heapq():
    def __init__(self,arr):
        self.que=[]
        for a in arr:
            self.que.append(-a)
        heapq.heapify(self.que)

    def pop(self):
        return -heapq.heappop(self.que)

    def push(self,a):
        heapq.heappush(self.que,-a)

    def top(self):
        return -self.que[0]

#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = 10**15
#################

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num

        for i in range(n):
            self.tree[self.num + i] = init_val[i]

        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

N=int(input())
beam=[tuple(map(int,input().split())) for i in range(N)]
beam.sort(key=lambda x:x[1])
data=[min(0,beam[i][0]-beam[i][1]) for i in range(N)]
for i in range(N-2,-1,-1):
    data[i]+=data[i+1]

cummin=[beam[i][1] for i in range(N)]
for i in range(N):
    if beam[i][0]-beam[i][1]>0:
        cummin[i]=10**10

for i in range(N-2,-1,-1):
    cummin[i]=min(cummin[i],cummin[i+1])

def cond(m):
    if m==0:
        if data[0]<=0:
            return True
        else:
            return False

    que=Heapq([])
    cnt=0
    S=0
    for i in range(N-1):
        if cnt==m:
            test=que.top()
            if beam[i][0]<test:
                que.pop()
                que.push(beam[i][0])
                S+=beam[i][0]-test
        else:
            que.push(beam[i][0])
            S+=beam[i][0]
            cnt+=1
        if cnt==m:
            test=S+data[i+1]
            if test<=0:
                return True
    return False

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if cond(test):
        start=test
    else:
        end=test

if not cond(0):
    exit(print(0,1))

m=start
ans=[0,1]
que=Heapq([])
cnt=0
S=0
if m!=0:
    for i in range(N-1):
        if cnt==m:
            test=que.top()
            if beam[i][0]<test:
                que.pop()
                que.push(beam[i][0])
                S+=beam[i][0]-test
        else:
            que.push(beam[i][0])
            S+=beam[i][0]
            cnt+=1
        if cnt==m:
            test=S+data[i+1]
            B=cummin[i+1]
            if test<=0:
                t=abs(test)
                if B*ans[0]<ans[1]*t:
                    ans=[t,B]

    start=[-1]*N
    end=[-1]*N
    que=[]
    trash=[]
    cnt=0
    S=0
    data1=[ide_ele]*N
    data2=[ide_ele]*N
    for i in range(N):
        if cnt==m:
            val,id=que[0]
            val=-val
            if val>beam[i][0]:
                heapq.heappop(que)
                heapq.heappush(trash,val)
                end[id]=i-1
                heapq.heappush(que,(-beam[i][0],i))
                start[i]=i
                S+=beam[i][0]-val
            else:
                heapq.heappush(trash,beam[i][0])
        else:
            heapq.heappush(que,(-beam[i][0],i))
            start[i]=i
            S+=beam[i][0]
            cnt+=1
        if cnt==m:
            if i!=N-1:
                data1[i]=S+data[i+1]
                if trash:
                    data2[i]=S+data[i+1]+trash[0]
                else:
                    data2[i]=S+data[i+1]
            else:
                data1[i]=S
                data2[i]=S+trash[0]
    for i in range(N):
        if start[i]!=-1 and end[i]==-1:
            end[i]=N-1

    Seg1=SegTree(data1,segfunc,ide_ele)
    Seg2=SegTree(data2,segfunc,ide_ele)
    for i in range(m):
        if end[i]==m-1:
            temp=Seg1.query(m,N)
            temp+=beam[i][0]-beam[i][1]
            if temp<=0:
                temp=abs(temp)
                B=beam[i][1]
                if B*ans[0]<ans[1]*temp:
                    ans=[t,B]
        else:
            L,R=m,end[i]
            temp=Seg2.query(L,R+1)-beam[i][0]
            temp+=beam[i][0]-beam[i][1]
            if temp<=0:
                temp=abs(temp)
                B=beam[i][1]
                if B*ans[0]<ans[1]*temp:
                    ans=[t,B]
            temp=Seg1.query(R+1,N)
            temp+=beam[i][0]-beam[i][1]
            if temp<=0:
                temp=abs(temp)
                B=beam[i][1]
                if B*ans[0]<ans[1]*temp:
                    ans=[t,B]
    for i in range(m,N):
        if beam[i][0]-beam[i][1]<=0 and 1:
            if start[i]==-1:
                temp=Seg1.query(i,N)
                temp+=beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[t,B]
            elif 1:
                L=start[i]
                R=end[i]
                temp=Seg2.query(L,R+1)-beam[i][0]
                temp+=beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[t,B]
                temp=Seg1.query(R+1,N)
                temp+=beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[t,B]
        else:
            if start[i]==-1 and 1:
                temp=Seg1.query(m-1,N)
                temp+=beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[t,B]
            else:
                if 1:
                    L=start[i]
                    R=end[i]
                    temp=Seg2.query(L,R+1)-beam[i][0]
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[t,B]
                    temp=min(Seg1.query(R+1,N),Seg1.query(m-1,L))
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[t,B]
else:
    for i in range(N):
        test=data[i]
        B=cummin[i]
        if test<=0:
            t=abs(test)
            if B*ans[0]<ans[1]*t:
                ans=[t,B]
    M=min(data)
    for i in range(N):
        if beam[i][0]-beam[i][1]>0:
            temp=M+beam[i][0]-beam[i][1]
            if temp<=0:
                temp=abs(temp)
                B=beam[i][1]
                if B*ans[0]<ans[1]*temp:
                    ans=[t,B]

p,q=ans
res=[q*m+p,N*q]
from math import gcd
g=gcd(res[0],res[1])
print(res[0]//g,res[1]//g)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

N = int(input())
S = 0
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b, b-a))
    else:
        Y.append((a, b, 0))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

def f(i, n):
    return S - YY[n] if n <= i else S - (YY[n+1] - Y[i][0])

maa, mab = 0, 1
for i in range(N):
    if Y[i][2] == 0: continue
    l = 0
    r = N
    while r - l > 1:
        m = (l+r) // 2
        if f(i, m) >= 0:
            l = m
        else:
            r = m
    
    aa = l * Y[i][1] + min(f(i, l), Y[i][1])
    bb = N * Y[i][1]
    if aa * mab > bb * maa:
        maa, mab = aa, bb
    
    
g = gcd(maa, mab)
print(maa//g, mab//g)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

N = int(input())
S = 0
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b, b-a))
    else:
        Y.append((a, b, 0))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

def f(i, n):
    return S - YY[n] if n <= i else S - (YY[n+1] - Y[i][0])

maa, mab = 0, 1
for i in range(N):
    if Y[i][2] == 0: continue
    l = 0
    r = N
    while r - l > 1:
        m = (l+r) // 2
        if f(i, m) >= 0:
            l = m
        else:
            r = m
    
    aa = l * Y[i][1] + f(i, l)
    bb = N * Y[i][1]
    if aa * mab > bb * maa:
        maa, mab = aa, bb
    
    
g = gcd(maa, mab)
print(maa//g, mab//g)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

N = int(input())
S = 0
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b, b-a))
    else:
        Y.append((a, b, 0))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

maa, mab = 0, 1
for i in range(N):
    if Y[i][2] == 0: continue
    l = 0
    r = N
    while r - l > 1:
        m = (l+r) // 2
        rem = S - YY[m] if m < i else S - (YY[m+1] - Y[i][0])
        if rem >= 0:
            l = m
        else:
            r = m

    aa = l * Y[i][1] + S - (YY[l] if l < i else YY[l+1] - Y[i][0])
    bb = N * Y[i][1]
    if aa * mab > bb * maa:
        maa, mab = aa, bb

g = gcd(maa, mab)
print(maa//g, mab//g)

Submission status: Wrong Answer

Solution code:
n = int(input())


from fractions import Fraction
a = [0]*n
b = [0]*n

for i in range(n):
    a[i],b[i] = map(int,input().split())

c = zip(a,b)
cc = sorted(c)

a,b = zip(*cc)
a = list(a)
b = list(b)


su = 0
ri = 0
win = 0
for i,c in enumerate(a):
    su = sum(a[0:i-1])
    ri = 0
    for j in range(i,n):
        su += a[j]
        ri += b[j]
        if su<ri:
            win += 1
            break

for i in range(2,win+1):
    f = True
    while(1):
        if win % i == 0 and n % i ==0:
            win = win/i
            n = n/i
        else:
            f = False
        if f == False:
            break

print(int(win),int(n))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def solve_d(n, a_list, b_list):
    a_list_sub = [a_list[i] for i in range(n) if a_list[i] < b_list[i]]
    b_list_sub = [b_list[i] for i in range(n) if a_list[i] < b_list[i]]
    a_list_add = [(a_list[i], i) for i in range(n) if a_list[i] >= b_list[i]]

    le = len(a_list_sub)
    if le == 0:
        return 0, 1
    a_sum = sum(a_list_sub)
    b_list_sub_s = sorted(b_list_sub, reverse=True)
    b_list_sub_cum = [0]
    for i, b in enumerate(b_list_sub_s):
        b_list_sub_cum.append(b_list_sub_cum[i] + b)

    r = bisect_left(b_list_sub_cum, a_sum) - 1
    q_max = b_list_sub_s[r]
    p_max = q_max * (le - r) - (a_sum - b_list_sub_cum[r])
    q_max *= n
    # print(le, p_max, q_max, r, a_sum - b_list_sub_cum[r])
    a_list_add_s = sorted(a_list_add, key=lambda x:x[0])
    for a, i in a_list_add_s:
        le += 1
        a_sum += a
        b_list_sub_cum.append(b_list_sub_cum[-1] + b_list[i])
        b_list_sub_s.append(b_list[i])

        r = bisect_left(b_list_sub_cum, a_sum) - 1
        if r >= len(b_list_sub_s):
            q = 1
            p = 0
        else:
            q = b_list_sub_s[r]
            p = q * (le - r) - (a_sum - b_list_sub_cum[r])
            q *= n
        # print(le, p, q)

        if p * q_max > p_max * q:
            p_max, q_max = p, q
    return p_max, q_max


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def main():
    n = int(input())
    a_list = [0] * n
    b_list = [0] * n
    for i in range(n):
        a, b = map(int, input().split())
        a_list[i] = a
        b_list[i] = b
    p, q = solve_d(n, a_list, b_list)
    r = gcd(p, q)
    print(p // r, q // r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

class Heapq():
    def __init__(self,arr):
        self.que=[]
        for a in arr:
            self.que.append(-a)
        heapq.heapify(self.que)

    def pop(self):
        return -heapq.heappop(self.que)

    def push(self,a):
        heapq.heappush(self.que,-a)

    def top(self):
        return -self.que[0]

#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = 10**15
#################

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num

        for i in range(n):
            self.tree[self.num + i] = init_val[i]

        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys,random

input=sys.stdin.readline

N=int(input())
beam=[tuple(map(int,input().split())) for i in range(N)]
def solve2():
    beam.sort(key=lambda x:x[1])
    data=[min(0,beam[i][0]-beam[i][1]) for i in range(N)]
    for i in range(N-2,-1,-1):
        data[i]+=data[i+1]

    cummin=[beam[i][1] for i in range(N)]
    for i in range(N):
        if beam[i][0]-beam[i][1]>0:
            cummin[i]=10**15

    for i in range(N-2,-1,-1):
        cummin[i]=min(cummin[i],cummin[i+1])

    def cond(m):
        if m==0:
            if data[0]<=0:
                return True
            else:
                return False

        que=Heapq([])
        cnt=0
        S=0
        for i in range(N-1):
            if cnt==m:
                test=que.top()
                if beam[i][0]<test:
                    que.pop()
                    que.push(beam[i][0])
                    S+=beam[i][0]-test
            else:
                que.push(beam[i][0])
                S+=beam[i][0]
                cnt+=1
            if cnt==m:
                test=S+data[i+1]
                if test<=0:
                    return True
        return False

    start=0
    end=N
    while end-start>1:
        test=(end+start)//2
        if cond(test):
            start=test
        else:
            end=test

    if not cond(0):
        exit(print(0,1))

    m=start
    ans=[0,1]
    que=Heapq([])
    cnt=0
    S=0
    if m!=0:
        for i in range(N-1):
            if cnt==m:
                test=que.top()
                if beam[i][0]<test:
                    que.pop()
                    que.push(beam[i][0])
                    S+=beam[i][0]-test
            else:
                que.push(beam[i][0])
                S+=beam[i][0]
                cnt+=1
            if cnt==m:
                test=S+data[i+1]
                B=cummin[i+1]
                if test<=0:
                    t=abs(test)
                    if B*ans[0]<ans[1]*t:
                        ans=[t,B]

        start=[-1]*N
        end=[-1]*N
        que=[]
        trash=[]
        cnt=0
        S=0
        data1=[ide_ele]*N
        data2=[ide_ele]*N
        for i in range(N):
            if cnt==m:
                val,id=que[0]
                val=-val
                if val>beam[i][0]:
                    heapq.heappop(que)
                    heapq.heappush(trash,val)
                    end[id]=i-1
                    heapq.heappush(que,(-beam[i][0],i))
                    start[i]=i
                    S+=beam[i][0]-val
                else:
                    heapq.heappush(trash,beam[i][0])
            else:
                heapq.heappush(que,(-beam[i][0],i))
                start[i]=i
                S+=beam[i][0]
                cnt+=1
            if cnt==m:
                if i!=N-1:
                    data1[i]=S+data[i+1]
                    if trash:
                        data2[i]=S+data[i+1]+trash[0]
                    else:
                        data2[i]=S+data[i+1]
                else:
                    data1[i]=S
                    data2[i]=S+trash[0]
        for i in range(N):
            if start[i]!=-1 and end[i]==-1:
                end[i]=N-1

        Seg1=SegTree(data1,segfunc,ide_ele)
        Seg2=SegTree(data2,segfunc,ide_ele)
        for i in range(m):
            if end[i]==m-1:
                temp=Seg1.query(m,N)
                temp+=beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[temp,B]
            else:
                L,R=m,end[i]
                temp=Seg2.query(L,R+1)-beam[i][0]
                temp+=beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[temp,B]
                temp=Seg1.query(R+1,N)
                temp+=beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[temp,B]
        for i in range(m,N):
            if beam[i][0]-beam[i][1]<=0:
                if start[i]==-1:
                    temp=Seg1.query(i,N)
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[temp,B]
                else:
                    L=start[i]
                    R=end[i]
                    temp=Seg2.query(L,R+1)-beam[i][0]
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[t,B]
                    temp=Seg1.query(R+1,N)
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[temp,B]
            else:
                if start[i]==-1:
                    temp=Seg1.query(m-1,N)
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[temp,B]
                else:
                    L=start[i]
                    R=end[i]
                    temp=Seg2.query(L,R+1)-beam[i][0]
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[temp,B]
                    temp=min(Seg1.query(R+1,N),Seg1.query(m-1,L))
                    temp+=beam[i][0]-beam[i][1]
                    if temp<=0:
                        temp=abs(temp)
                        B=beam[i][1]
                        if B*ans[0]<ans[1]*temp:
                            ans=[temp,B]

    else:
        for i in range(N):
            test=data[i]
            B=cummin[i]
            if test<=0:
                t=abs(test)
                if B*ans[0]<ans[1]*t:
                    ans=[t,B]
        M=min(data)
        for i in range(N):
            if beam[i][0]-beam[i][1]>0:
                temp=M+beam[i][0]-beam[i][1]
                if temp<=0:
                    temp=abs(temp)
                    B=beam[i][1]
                    if B*ans[0]<ans[1]*temp:
                        ans=[temp,B]

    p,q=ans
    res=[q*m+p,N*q]
    from math import gcd
    g=gcd(res[0],res[1])
    return (res[0]//g,res[1]//g)

print(*solve2())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return a

N = int(input())
S = 0
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b))
    else:
        Y.append((a, b))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

# i番目を除いてn個選ぶときの余裕度
def f(i, n):
    return S - Y[i][0] + Y[i][1] - (YY[n] if n <= i else YY[n+1] - Y[i][0])

ma1, ma2 = 0, 1
for i in range(N):
    l = 0
    r = N
    while r - l > 1:
        m = (l+r) // 2
        if f(i, m) >= 0:
            l = m
        else:
            r = m

    a = l * Y[i][1] + min(f(i, l), Y[i][1])
    b = N * Y[i][1]
    if a * ma2 > b * ma1:
        ma1, ma2 = a, b

g = gcd(ma1, ma2)
print(ma1//g, ma2//g)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return a

N = int(input())
S = 0
Y = []
for i in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b, b-a, 0))
    else:
        Y.append((a, b, 0, a-b))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

def f(i, n):
    if Y[i][2]:
        return S - YY[n] if n <= i else S - (YY[n+1] - Y[i][0])
    return S - Y[i][3] - YY[n] if n <= i else S - Y[i][3] - (YY[n+1] - Y[i][0])

maa, mab = 0, 1
for i in range(N):
    l = 0
    r = N
    while r - l > 1:
        m = (l+r) // 2
        if f(i, m) >= 0:
            l = m
        else:
            r = m

    a = l * Y[i][1] + min(f(i, l), Y[i][1])
    b = N * Y[i][1]
    if a * mab > b * maa:
        maa, mab = a, b

g = gcd(maa, mab)
print(maa//g, mab//g)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappushpop, heapify
from fractions import gcd

N = int(readline())
m = map(int,read().split())
AB = sorted(zip(m,m),key=lambda x:(x[1],x[0]))
A,B = zip(*AB)

dp2 = [0]*N # T_B - T_A
for i in range(N-1,0,-1):
    a = A[i]; b = B[i]
    if a<b:
        dp2[i-1] = dp2[i]+(b-a)
    else:
        dp2[i-1] = dp2[i]

def F(n):
    opt_num = -1
    opt_den = 1
    q = list(-x for x in A[:n])
    heapify(q)
    S = -sum(q)
    for i in range(n,N):
        a = A[i]; b = B[i]
        x = S+a-dp2[i]
        if 0<=x<=b:
            den = b
            num = (n+1)*den-x
            if opt_num*den < opt_den*num:
                opt_num = num; opt_den = den
        x = a
        y = -heappushpop(q,-x)
        S += x-y
    return opt_num, opt_den

opt_num = 0; opt_den = 1
left = -1 # 値がある
right = N+10 # むり
while left+1 < right:
    mid = (left+right)//2
    num,den = F(mid)
    if num==-1:
        right=mid
    else:
        left=mid
        if opt_num*den < opt_den*num:
            opt_num = num; opt_den = den

opt_den *= N
g = gcd(opt_num,opt_den)
opt_num//=g; opt_den//=g
print(opt_num,opt_den)

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
from operator import itemgetter


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        sum = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum + self.tree[k] < x:
                sum += self.tree[k]
                pos += 1 << i
        return pos + 1, sum


def solve(n, dec, inc):
    # dec: 距離を縮められる平均台
    # inc: 離される平均台
    if len(dec) == 0:
        print(0, 1)
        return

    # 基本は縮められる平均台を左に、離される平均台を右に。
    # 右突入までに追いつけるかが勝負。
    # ただし、離されてもすぬけくんの所要時間が短いものは、
    # りんごさんの初期位置の確率UPのため左に持っていく価値があるものもある

    _rng_list = rng_list
    _rng_dict = rng_dict

    dec.sort(key=itemgetter(1))
    inc.sort()

    dec_snk, dec_rng = zip(*dec)
    inc_snk, inc_rng = zip(*inc)
    dec_snk_sum = sum(dec_snk)

    ld = len(dec)
    lr = len(_rng_list)

    bit = Bit(lr)
    for b in dec_rng:
        bit.add(_rng_dict[b] + 1, b)

    # 左に inc の平均台が1つも無い状態
    j, full = bit.lower_bound(dec_snk_sum)
    best_denominator = 1
    best_numerator = ld - (j - 1)
    if j <= lr:
        best_denominator = _rng_list[j - 1]
        best_numerator = best_numerator * best_denominator - (dec_snk_sum - full)
    best = best_numerator / best_denominator

    for i in range(len(inc)):
        # inc の i 番目の平均台を左で使う
        dec_snk_sum += inc_snk[i]
        b = inc_rng[i]
        bit.add(_rng_dict[b] + 1, b)
        j, full = bit.lower_bound(dec_snk_sum)
        denominator = 1
        numerator = ld + (i + 1) - (j - 1)
        if j <= lr:
            denominator = _rng_list[j - 1]
            numerator = numerator * denominator - (dec_snk_sum - full)
        tmp_best = numerator / denominator

        if best < tmp_best:
            best = tmp_best
            best_denominator = denominator
            best_numerator = numerator

    best_denominator *= n
    g = gcd(best_numerator, best_denominator)
    print(best_numerator // g, best_denominator // g)


n = int(input())
dec = []
inc = []
compress = set()

for line in sys.stdin:
    a, b = map(int, line.split())
    if a < b:
        dec.append((a, b))
    else:
        inc.append((a, b))
    compress.add(b)

rng_list = sorted(compress, reverse=True)
rng_dict = {b: i for i, b in enumerate(rng_list)}
# print(rng_list)
# print(rng_dict)

solve(n, dec, inc)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

N = int(input())
S = 0
Y = []
for _ in range(N):
    a, b = map(int, input().split())
    if b > a:
        S += b-a
        Y.append((b, b))
    else:
        Y.append((a, b))

Y = sorted(Y)
YY = [0] * (N+1)
for i in range(N):
    YY[i+1] = YY[i] + Y[i][0]

l = 0
r = N
while r - l > 1:
    m = (l+r) // 2
    if S - YY[m] >= 0:
        l = m
    else:
        r = m

a = l * Y[l+1][1] + S - YY[l]
b = N * Y[l+1][1]
g = gcd(a, b)

print(a//g, b//g)

Submission status: Runtime Error

Solution code:
from fractions import Fraction

lst = []

n = int(input())
s = 0

for i in range (n) :
    (a, b) = input().split(" ")
    a = int(a)
    b = int(b)
    s += a
    lst.append(a-b)

lst.sort()

ans = Fraction(0, 1)

for i in range(n) :
    if s > 0 && s + lst[i] < 0 :
        ans += Fraction(-lst[i]-s,-lst[i]*n)
    elif s < 0 && s + lst[i] > 0 :
        ans += Fraction(-s, lst[i]*n)
    elif s < 0 :
        ans += Fraction(1, n)

print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left


def solve_d(n, a_list, b_list):
    a_list_sub = [a_list[i] for i in range(n) if a_list[i] < b_list[i]]
    b_list_sub = [b_list[i] for i in range(n) if a_list[i] < b_list[i]]
    a_list_add = [(a_list[i], i) for i in range(n) if a_list[i] >= b_list[i]]

    le = len(a_list_sub)
    if le == 0:
        return 0, 1
    a_sum = sum(a_list_sub)
    b_list_sub_s = sorted(b_list_sub, reverse=True)
    b_list_sub_cum = [0]
    for i, b in enumerate(b_list_sub_s):
        b_list_sub_cum.append(b_list_sub_cum[i] + b)

    r = bisect_left(b_list_sub_cum, a_sum) - 1
    q_max = b_list_sub_s[r]
    p_max = q_max * (le - r) - (a_sum - b_list_sub_cum[r])
    q_max *= n
    # print(le, p_max, q_max, r, a_sum - b_list_sub_cum[r])
    a_list_add_s = sorted(a_list_add, key=lambda x:x[0])
    for a, i in a_list_add_s:
        le += 1
        a_sum += a
        b_list_sub_cum.append(b_list_sub_cum[-1] + b_list[i])
        b_list_sub_s.append(b_list[i])

        r = bisect_left(b_list_sub_cum, a_sum) - 1
        q = b_list_sub_s[r]
        p = q * (le - r) - (a_sum - b_list_sub_cum[r])
        q *= n
        # print(le, p, q)

        if p * q_max > p_max * q:
            p_max, q_max = p, q
    return p_max, q_max


def gcd(x, y):
    while y:
        x, y = y, x % y
    return x


def main():
    n = int(input())
    a_list = [0] * n
    b_list = [0] * n
    for i in range(n):
        a, b = map(int, input().split())
        a_list[i] = a
        b_list[i] = b
    p, q = solve_d(n, a_list, b_list)
    r = gcd(p, q)
    print(p // r, q // r)


if __name__ == "__main__":
    main()