結果

問題 No.3073 Fraction Median
ユーザー titia
提出日時 2025-03-21 23:13:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 698 bytes
コンパイル時間 422 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 302,296 KB
最終ジャッジ日時 2025-03-21 23:13:29
合計ジャッジ時間 6,434 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from math import gcd
from bisect import bisect

N=int(input())
A=list(map(int,input().split()))

A.sort()

B=[]

for a in A:
    B.append((1<<100)//a)

B.reverse()

OK=1<<200
NG=0

while OK>NG+1:
    mid=(OK+NG)//2

    score=0

    for a in A:
        k=mid//a+1

        x=bisect(B,k)
        score+=x

    if score>=N*(N-1)//2:
        OK=mid
    else:
        NG=mid

#print(OK)

SA=set(A)

for i in range(len(B)):
    k=OK/B[i]
    kx=round(k)

    if abs(k-kx)<0.000000001 and kx in SA:
        #print(kx,A[len(A)-1-i])

        a=kx
        b=A[len(A)-1-i]

        GCD=gcd(a,b)

        a//=GCD
        b//=GCD

        print(a,b)
        break
0