結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:27:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,009 bytes
記録
コンパイル時間 336 ms
コンパイル使用メモリ 81,844 KB
実行使用メモリ 80,312 KB
最終ジャッジ日時 2025-04-16 00:29:22
合計ジャッジ時間 10,679 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28 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

    # Generate AB array
    AB = []
    for w in range(K):
        a = A[w]
        for x in range(L):
            b = B[x]
            ab = a * b
            AB.append((ab, w, x))
    # Generate CD array
    CD = []
    for y in range(M):
        c = C[y]
        for z in range(N):
            d = D[z]
            cd = c * d
            CD.append((cd, y, z))
    # Sort AB and CD by their product values
    AB.sort(key=lambda t: t[0])
    CD.sort(key=lambda t: t[0])
    CD_values = [t[0] for t in CD]

    # Compute initial low and high for binary search
    if not AB or not CD:
        print(0)
        print(0, 0, 0, 0)
        return

    ab_min = AB[0][0]
    ab_max = AB[-1][0]
    cd_min = CD[0][0]
    cd_max = CD[-1][0]

    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 to find T
    T = 0
    while low <= high:
        mid = (low + high) // 2
        # Calculate how many elements <= mid
        cnt = 0
        for ab, w, x in AB:
            if ab == 0:
                if mid >= 0:
                    cnt += len(CD)
                continue
            target = mid // ab
            rem = mid % ab
            if ab > 0:
                # CD[j] <= target
                pos = bisect.bisect_right(CD_values, target)
                cnt += pos
            else:
                # ab <0, CD[j] >= ceil(mid/ab)
                if rem == 0:
                    ceil_val = target
                else:
                    ceil_val = target + 1
                pos = bisect.bisect_left(CD_values, ceil_val)
                cnt += len(CD_values) - pos
        if cnt >= S:
            T = mid
            high = mid - 1
        else:
            low = mid + 1

    # Now find a combination a,b,c,d such that a*b*c*d = T
    a = b = c = d = None
    found = False
    # Check AB and CD
    for ab_val, w, x in AB:
        if ab_val == 0:
            if T == 0:
                # Any CD element will do
                cd_val, y, z = CD[0]
                a = A[w]
                b = B[x]
                c = C[y]
                d = D[z]
                found = True
                break
            else:
                continue
        if T % ab_val != 0:
            continue
        required_cd = T // ab_val
        # Find in CD
        pos = bisect.bisect_left(CD_values, required_cd)
        if pos < len(CD_values) and CD_values[pos] == required_cd:
            # Check all possible positions (might have duplicates)
            # Take the first occurrence
            cd_val, y, z = CD[pos]
            a = A[w]
            b = B[x]
            c = C[y]
            d = D[z]
            found = True
            break
    if not found and T == 0:
        # Check if any AB is zero and CD is any
        for ab_val, w, x in AB:
            if ab_val == 0:
                cd_val, y, z = CD[0]
                a = A[w]
                b = B[x]
                c = C[y]
                d = D[z]
                found = True
                break
        if not found:
            # Check if any CD is zero
            for cd_val, y, z in CD:
                if cd_val == 0:
                    ab_val, w, x = AB[0]
                    a = A[w]
                    b = B[x]
                    c = C[y]
                    d = D[z]
                    found = True
                    break

    print(T)
    print(a, b, c, d)

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