結果

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

ソースコード

diff #
raw source code 

import bisect

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
    AB = []
    for w in range(K):
        a = A[w]
        for x in range(L):
            b = B[x]
            ab_product = a * b
            AB.append( (ab_product, w, x) )
    AB.sort()
    AB_products = [ab[0] for ab in AB]

    # Compute CD
    CD = []
    for y in range(M):
        c = C[y]
        for z in range(N):
            d = D[z]
            cd_product = c * d
            CD.append( (cd_product, y, z) )
    CD.sort()
    CD_products = [cd[0] for cd in CD]

    # Binary search for T

    # Compute possible min and max
    min_ab = AB_products[0] if AB else 0
    max_ab = AB_products[-1] if AB else 0
    min_cd = CD_products[0] if CD else 0
    max_cd = CD_products[-1] if CD else 0
    possible_products = [
        min_ab * min_cd,
        min_ab * max_cd,
        max_ab * min_cd,
        max_ab * max_cd
    ]
    low = min(possible_products)
    high = max(possible_products)

    # Binary search
    left = low
    right = high

    def count_less_equal(T):
        cnt = 0
        for ab in AB:
            a = ab[0]
            if a == 0:
                if T >= 0:
                    cnt += len(CD)
                continue
            # Compute target
            target = T / a
            # Check if target makes sense
            if a > 0:
                if CD_products[-1] < target:
                    cnt += len(CD)
                    continue
                if CD_products[0] > target:
                    continue
                idx = bisect.bisect_right(CD_products, target)
                cnt += idx
            else:
                if CD_products[0] > target:
                    cnt += len(CD)
                    continue
                if CD_products[-1] < target:
                    continue
                idx = bisect.bisect_left(CD_products, target)
                cnt += len(CD_products) - idx
        return cnt

    while left < right:
        mid = (left + right) // 2
        cnt = count_less_equal(mid)
        if cnt < S:
            left = mid + 1
        else:
            right = mid

    T = left

    # Now find a and c

    # Precompute CD's product to (y, z) map
    cd_dict = {}
    for c in CD:
        p = c[0]
        if p not in cd_dict:
            cd_dict[p] = []
        cd_dict[p].append( (c[1], c[2]) )

    for ab in AB:
        a = ab[0]
        if a == 0:
            if T == 0:
                # find any c with product 0
                if 0 in cd_dict:
                    c_y, c_z = cd_dict[0][0]
                    print(T)
                    print(A[ab[1]], B[ab[2]], C[c_y], D[c_z])
                    return
            continue
        if T % a != 0:
            continue
        target = T // a
        if target in cd_dict:
            c_y, c_z = cd_dict[target][0]
            print(T)
            print(A[ab[1]], B[ab[2]], C[c_y], D[c_z])
            return

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