結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:43:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,408 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 163,028 KB
最終ジャッジ日時 2025-06-12 21:47:42
合計ジャッジ時間 10,229 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 WA * 1 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 CD
    AB = []
    for i in range(K):
        a = A[i]
        for j in range(L):
            b = B[j]
            AB.append((a * b, i, j))
    AB.sort(key=lambda x: x[0])

    CD = []
    for k in range(M):
        c = C[k]
        for l in range(N):
            d = D[l]
            CD.append((c * d, k, l))
    CD.sort(key=lambda x: x[0])

    # Build CD dictionary and values list
    cd_dict = defaultdict(list)
    cd_values = []
    for val, k, l in CD:
        cd_dict[val].append((k, l))
        cd_values.append(val)

    # Binary search to find T
    if not AB or not CD:
        print(0)
        print(*([0]*4))
        return

    min_ab = AB[0][0]
    max_ab = AB[-1][0]
    min_cd = CD[0][0]
    max_cd = CD[-1][0]

    candidates = [min_ab * min_cd, min_ab * max_cd, max_ab * min_cd, max_ab * max_cd]
    low = min(candidates)
    high = max(candidates)

    while low < high:
        mid = (low + high) // 2
        count = 0

        for ab_tuple in AB:
            ab_val = ab_tuple[0]
            if ab_val == 0:
                if mid >= 0:
                    count += len(CD)
                continue
            if ab_val > 0:
                target = mid // ab_val
                cnt = bisect.bisect_right(cd_values, target)
                count += cnt
            else:
                target = mid / ab_val
                idx = bisect.bisect_left(cd_values, target)
                count += len(cd_values) - idx

        if count >= S:
            high = mid
        else:
            low = mid + 1
    T = low

    # Find a, b, c, d
    for ab_tuple in AB:
        ab_val, i, j = ab_tuple
        if ab_val == 0:
            if T != 0:
                continue
            # T is 0
            # Find a and b such that a*b ==0
            a = None
            b = None
            # Check A
            for a_val in A:
                if a_val == 0:
                    a = a_val
                    b = B[j]
                    break
            if a is None:
                # Check B
                for b_val in B:
                    if b_val == 0:
                        b = b_val
                        a = A[i]
                        break
            # Choose first element in CD
            cd_tuple = CD[0]
            c = C[cd_tuple[1]]
            d = D[cd_tuple[2]]
            print(T)
            print(a, b, c, d)
            return
        else:
            if T % ab_val != 0:
                continue
            target = T // ab_val
            if target in cd_dict:
                k, l = cd_dict[target][0]
                a = A[i]
                b = B[j]
                c = C[k]
                d = D[l]
                print(T)
                print(a, b, c, d)
                return

    # Fallback in case nothing found (should not happen)
    print(0)
    print(0, 0, 0, 0)

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