結果

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

ソースコード

diff # 

import bisect
import math
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
    
    # Generate AB and CD pairs with indices (1-based)
    ab_list = []
    for i in range(K):
        a = A[i]
        for j in range(L):
            b = B[j]
            ab = a * b
            ab_list.append( (ab, i+1, j+1) )  # 1-based indices
    
    cd_list = []
    for i in range(M):
        c = C[i]
        for j in range(N):
            d = D[j]
            cd = c * d
            cd_list.append( (cd, i+1, j+1) )
    
    # Sort AB and CD by their product values
    ab_list.sort(key=lambda x: x[0])
    cd_list.sort(key=lambda x: x[0])
    
    ab_values = [x[0] for x in ab_list]
    cd_values = [x[0] for x in cd_list]
    
    # Precompute min and max for AB and CD
    a_min = min(A)
    a_max = max(A)
    b_min = min(B)
    b_max = max(B)
    ab_candidates = [a_min*b_min, a_min*b_max, a_max*b_min, a_max*b_max]
    ab_min = min(ab_candidates)
    ab_max = max(ab_candidates)
    
    c_min = min(C)
    c_max = max(C)
    d_min = min(D)
    d_max = max(D)
    cd_candidates = [c_min*d_min, c_min*d_max, c_max*d_min, c_max*d_max]
    cd_min = min(cd_candidates)
    cd_max = max(cd_candidates)
    
    # Compute initial low and high for binary search
    candidates_low = [ab_min * cd_min, ab_min * cd_max, ab_max * cd_min, ab_max * cd_max]
    candidates_high = candidates_low.copy()
    low = min(candidates_low)
    high = max(candidates_high)
    
    # Function to count numbers <= X
    def count(X):
        total = 0
        for cd_val in cd_values:
            if cd_val > 0:
                q = X // cd_val
                cnt = bisect.bisect_right(ab_values, q)
                total += cnt
            elif cd_val < 0:
                if cd_val == 0:
                    continue
                ceil_val = math.ceil(X / cd_val)
                idx = bisect.bisect_left(ab_values, ceil_val)
                cnt = len(ab_values) - idx
                total += cnt
            else:  # cd_val == 0
                if X >= 0:
                    total += len(ab_values)
        return total
    
    # Binary search
    answer = None
    while low <= high:
        mid = (low + high) // 2
        c = count(mid)
        if c >= S:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    
    T = answer
    
    # Now find a, b, c, d such that a*b*c*d = T
    # Preprocess cd_dict for quick lookup
    cd_dict = defaultdict(list)
    for idx, (val, c_idx, d_idx) in enumerate(cd_list):
        cd_dict[val].append( (c_idx, d_idx) )
    
    found = False
    result = None
    
    if T == 0:
        # Check if any ab is zero
        for ab in ab_list:
            if ab[0] == 0:
                a_idx = ab[1]
                b_idx = ab[2]
                # Any cd will do, take the first one
                if cd_list:
                    cd = cd_list[0]
                    c_idx = cd[1]
                    d_idx = cd[2]
                    a = A[a_idx-1]
                    b = B[b_idx-1]
                    c = C[c_idx-1]
                    d = D[d_idx-1]
                    result = (a, b, c, d)
                    found = True
                    break
        if not found:
            # Check if any cd is zero
            for cd in cd_list:
                if cd[0] == 0:
                    c_idx = cd[1]
                    d_idx = cd[2]
                    # Any ab will do, take the first one
                    if ab_list:
                        ab = ab_list[0]
                        a_idx = ab[1]
                        b_idx = ab[2]
                        a = A[a_idx-1]
                        b = B[b_idx-1]
                        c = C[c_idx-1]
                        d = D[d_idx-1]
                        result = (a, b, c, d)
                        found = True
                        break
    else:
        # Check each ab in ab_list
        for ab in ab_list:
            ab_val, a_idx_ab, b_idx_ab = ab
            if ab_val == 0:
                continue
            if T % ab_val != 0:
                continue
            required_cd = T // ab_val
            # Check if required_cd exists in cd_dict
            if required_cd in cd_dict:
                # Get any (c_idx, d_idx) for this cd_val
                c_idx_cd, d_idx_cd = cd_dict[required_cd][0]
                a_val = A[a_idx_ab - 1]
                b_val = B[b_idx_ab - 1]
                c_val = C[c_idx_cd - 1]
                d_val = D[d_idx_cd - 1]
                result = (a_val, b_val, c_val, d_val)
                found = True
                break
    
    # Output
    print(T)
    if result:
        a, b, c, d = result
        print(f"{a} {b} {c} {d}")

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