結果

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