結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:13:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,562 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 82,760 KB
実行使用メモリ 128,684 KB
最終ジャッジ日時 2025-06-12 13:16:07
合計ジャッジ時間 10,670 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28 TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

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

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

    # Generate AB pairs (product, a_idx, b_idx)
    AB = []
    for a_idx in range(K):
        a = A[a_idx]
        for b_idx in range(L):
            b = B[b_idx]
            prod = a * b
            AB.append((prod, a_idx, b_idx))
    # Sort AB by product
    AB.sort()

    # Generate CD pairs (product, c_idx, d_idx)
    CD = []
    for c_idx in range(M):
        c = C[c_idx]
        for d_idx in range(N):
            d = D[d_idx]
            prod = c * d
            CD.append((prod, c_idx, d_idx))
    # Sort CD by product
    CD.sort()

    # Extract products for binary search
    AB_products = [x[0] for x in AB]
    CD_products = [x[0] for x in CD]

    # Function to count the number of elements <= X
    def count_le(X):
        count = 0
        # Iterate through each AB product
        for p in AB_products:
            if p == 0:
                if X >= 0:
                    count += len(CD_products)
                continue
            # Find the number of CD products q where p*q <= X
            if p > 0:
                max_q = X // p
                if p * max_q > X:
                    max_q -= 1
                # Find the rightmost q <= max_q
                cnt = bisect.bisect_right(CD_products, max_q)
                count += cnt
            else:
                # p < 0: q >= X/p (since p is negative, division flips inequality)
                min_q = X // p
                if X % p != 0:
                    min_q += 1
                # Find the first q >= min_q
                cnt = len(CD_products) - bisect.bisect_left(CD_products, min_q)
                count += cnt
        return count

    # Binary search for the smallest X where count_le(X) >= S
    low = -10**18
    high = 10**18
    answer = None
    while low <= high:
        mid = (low + high) // 2
        cnt = count_le(mid)
        if cnt >= S:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1

    T = answer

    # Now find a combination that produces T
    found = False
    a_ans = b_ans = c_ans = d_ans = None
    # Check AB and CD pairs
    for p, a_idx, b_idx in AB:
        if p == 0:
            if T == 0:
                # Any CD pair will do
                if CD:
                    c_val, c_idx_cd, d_idx_cd = CD[0]
                    a_ans = A[a_idx]
                    b_ans = B[b_idx]
                    c_ans = C[c_idx_cd]
                    d_ans = D[d_idx_cd]
                    found = True
                    break
            continue
        if T % p != 0:
            continue
        target_q = T // p
        # Search in CD_products
        idx_q = bisect.bisect_left(CD_products, target_q)
        if idx_q < len(CD_products) and CD_products[idx_q] == target_q:
            # Find any occurrence
            while idx_q < len(CD_products) and CD_products[idx_q] == target_q:
                c_val, c_idx_cd, d_idx_cd = CD[idx_q]
                a_ans = A[a_idx]
                b_ans = B[b_idx]
                c_ans = C[c_idx_cd]
                d_ans = D[d_idx_cd]
                found = True
                break
            if found:
                break
    if not found:
        # Check if T is zero and there are zero in CD
        if T == 0:
            # Check if any CD is zero
            for q, c_idx_cd, d_idx_cd in CD:
                if q == 0:
                    # Find any AB with any p
                    a_ans = A[0]
                    b_ans = B[0]
                    c_ans = C[c_idx_cd]
                    d_ans = D[d_idx_cd]
                    found = True
                    break
            if not found:
                # Check if any AB is zero
                for p, a_idx, b_idx in AB:
                    if p == 0:
                        # Any CD
                        c_ans = C[0]
                        d_ans = D[0]
                        a_ans = A[a_idx]
                        b_ans = B[b_idx]
                        found = True
                        break

    print(T)
    print(a_ans, b_ans, c_ans, d_ans)

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