結果

問題 No.3073 Fraction Median
ユーザー titia
提出日時 2025-03-21 23:14:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 696 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 280,148 KB
最終ジャッジ日時 2025-03-21 23:14:38
合計ジャッジ時間 6,190 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 3 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<<60)//a)

B.reverse()

OK=1<<90
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