結果

問題 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
    
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0