結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:37:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,913 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 151,296 KB
最終ジャッジ日時 2025-06-12 21:40:35
合計ジャッジ時間 12,786 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 8 TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    K = int(input[ptr])
    ptr += 1
    L = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    N = int(input[ptr])
    ptr += 1
    S = int(input[ptr])
    ptr += 1

    A = list(map(int, input[ptr:ptr+K]))
    ptr += K
    B = list(map(int, input[ptr:ptr+L]))
    ptr += L
    C = list(map(int, input[ptr:ptr+M]))
    ptr += M
    D = list(map(int, input[ptr:ptr+N]))
    ptr += N

    # Compute AB and ab_dict
    AB = []
    ab_dict = defaultdict(list)
    for a in A:
        for b in B:
            product = a * b
            AB.append(product)
            ab_dict[product].append((a, b))
    AB.sort()

    # Compute CD and cd_dict
    CD = []
    cd_dict = defaultdict(list)
    for c in C:
        for d in D:
            product = c * d
            CD.append(product)
            cd_dict[product].append((c, d))
    CD.sort()

    # Function to count pairs (ab, cd) where ab*cd <= T
    def count_pairs(T):
        count = 0
        for ab in AB:
            if ab == 0:
                if T >= 0:
                    count += len(CD)
            else:
                if ab > 0:
                    required = T / ab
                    cnt = bisect.bisect_right(CD, required)
                    count += cnt
                else:
                    required = T / ab
                    cnt = len(CD) - bisect.bisect_left(CD, required)
                    count += cnt
        return count

    # Determine initial low and high
    ab_min = min(AB)
    ab_max = max(AB)
    cd_min = min(CD)
    cd_max = max(CD)
    candidates = [
        ab_min * cd_min,
        ab_min * cd_max,
        ab_max * cd_min,
        ab_max * cd_max
    ]
    low = min(candidates)
    high = max(candidates)

    # Binary search for T
    while low < high:
        mid = (low + high) // 2
        cnt = count_pairs(mid)
        if cnt >= S:
            high = mid
        else:
            low = mid + 1
    T = low

    # Find a and b from AB, c and d from CD such that ab * cd == T
    success = False
    for ab in AB:
        if ab == 0:
            if T == 0:
                cd = CD[0]
                a, b = ab_dict[ab][0]
                c, d = cd_dict[cd][0]
                print(T)
                print(a, b, c, d)
                success = True
                break
        else:
            if T % ab == 0:
                required_cd = T // ab
                idx = bisect.bisect_left(CD, required_cd)
                if idx < len(CD) and CD[idx] == required_cd:
                    a, b = ab_dict[ab][0]
                    c, d = cd_dict[required_cd][0]
                    print(T)
                    print(a, b, c, d)
                    success = True
                    break
    if not success:
        pass

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