結果

問題 No.3073 Fraction Median
ユーザー i_taku
提出日時 2025-03-25 16:48:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,523 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 83,032 KB
実行使用メモリ 53,700 KB
最終ジャッジ日時 2025-03-25 16:49:07
合計ジャッジ時間 9,779 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd
from heapq import heappop, heappush


class Fraction:
    def __init__(self, x, y):
        g = gcd(x, y)
        self.x = x // g
        self.y = y // g

    def __lt__(self, other):
        return self.x * other.y < other.x * self.y
    
    def __le__(self, other):
        return self.x * other.y <= other.x * self.y
    
    def __gt__(self, other):
        return self.x * other.y > other.x * self.y

    def __ge__(self, other):
        return self.x * other.y >= other.x * self.y
    
    def __eq__(self, other):
        return self.x * other.y == other.x * self.y

def upd(i, j):
    if i < N:
        if i + 1 != j:
            if (i + 1, j) not in vis:
                heappush(hq, (Fraction(A[i + 1], A[j]), i + 1, j))
                vis.add((i + 1, j))
        elif i + 2 < N:
            if (i + 2, j) not in vis:
                heappush(hq, (Fraction(A[i + 1], A[j]), i + 2, j))
                vis.add((i + 2, j))
    if 0 < j:
        if j - 1 != i:
            if (i, j - 1) not in vis:
                heappush(hq, (Fraction(A[i], A[j - 1]), i, j - 1))
                vis.add((i, j - 1))
        elif i < j - 2:
            if (i, j - 2) not in vis:
                heappush(hq, (Fraction(A[i], A[j - 1]), i, j - 2))
                vis.add((i, j - 2))

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

hq = [(Fraction(A[0], A[-1]), 0, N - 1)]
vis.add((0, N - 1))
for _ in range(N * (N - 1) // 2):
    f, i, j = heappop(hq)
    upd(i, j)
print(f.x, f.y)
0