結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
ユーザー gew1fw
提出日時 2025-06-12 16:46:14
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,880 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 141,416 KB
最終ジャッジ日時 2025-06-12 16:46:46
合計ジャッジ時間 10,764 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 RE * 1 TLE * 4 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    K = int(data[idx])
    L = int(data[idx+1])
    M = int(data[idx+2])
    N = int(data[idx+3])
    S = int(data[idx+4])
    idx +=5
    
    A = list(map(int, data[idx:idx+K]))
    idx += K
    B = list(map(int, data[idx:idx+L]))
    idx += L
    C = list(map(int, data[idx:idx+M]))
    idx += M
    D = list(map(int, data[idx:idx+N]))
    idx += N
    
    # Compute AB and AB_map
    AB = []
    AB_map = {}
    for a in A:
        for b in B:
            ab = a * b
            if ab not in AB_map:
                AB_map[ab] = (a, b)
            AB.append(ab)
    AB.sort()
    
    # Compute CD and CD_map
    CD = []
    CD_map = {}
    for c in C:
        for d in D:
            cd = c * d
            if cd not in CD_map:
                CD_map[cd] = (c, d)
            CD.append(cd)
    CD.sort()
    
    cd_set = set(CD)
    
    # Helper function to count the number of pairs (ab, cd) where ab*cd <= T.
    def count_less_or_equal(T):
        count = 0
        for ab in AB:
            if ab == 0:
                if T >= 0:
                    count += len(CD)
            else:
                if ab > 0:
                    if T < ab * CD[-1]:
                        max_cd = T // ab
                        cnt = bisect.bisect_right(CD, max_cd)
                        count += cnt
                    else:
                        count += len(CD)
                else:
                    min_cd = T / ab
                    idx = bisect.bisect_left(CD, min_cd)
                    count += len(CD) - idx
        return count
    
    # Find the minimal and maximal possible T
    min_ab = min(AB)
    max_ab = max(AB)
    min_cd = min(CD)
    max_cd = max(CD)
    
    candidates = [
        min_ab * min_cd,
        min_ab * max_cd,
        max_ab * min_cd,
        max_ab * max_cd
    ]
    low = min(candidates)
    high = max(candidates)
    
    # Binary search
    while low < high:
        mid = (low + high) // 2
        cnt = count_less_or_equal(mid)
        if cnt >= S:
            high = mid
        else:
            low = mid + 1
    
    T = low
    
    # Now, find ab and cd such that ab * cd = T
    ab_val = None
    cd_val = None
    for ab in AB:
        if ab == 0:
            if T == 0:
                if 0 in cd_set:
                    ab_val = ab
                    cd_val = 0
                    break
        else:
            if T % ab != 0:
                continue
            target = T // ab
            if target in cd_set:
                ab_val = ab
                cd_val = target
                break
    
    # Retrieve a and b from AB_map, c and d from CD_map
    a, b = AB_map[ab_val]
    c, d = CD_map[cd_val]
    
    print(T)
    print(f"{a} {b} {c} {d}")

if __name__ == "__main__":
    main()
0