結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:50:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,453 bytes
記録
コンパイル時間 351 ms
コンパイル使用メモリ 82,900 KB
実行使用メモリ 81,432 KB
最終ジャッジ日時 2025-03-31 17:51:34
合計ジャッジ時間 12,582 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 11 TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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 and CD arrays
    AB = []
    for a in A:
        for b in B:
            AB.append( (a*b, a, b) )
    AB.sort(key=lambda x: x[0])
    ab_values = [x[0] for x in AB]
    
    CD = []
    for c in C:
        for d in D:
            CD.append( (c*d, c, d) )
    CD.sort(key=lambda x: x[0])
    cd_values = [x[0] for x in CD]
    
    # Binary search for T
    left = -10**18
    right = 10**18
    T = 0
    while left <= right:
        mid = (left + right) // 2
        count = 0
        # Iterate through all AB and calculate CD's allowed range
        ab_ptr = 0
        while ab_ptr < len(AB):
            ab = AB[ab_ptr][0]
            # Handle zero case
            if ab == 0:
                if mid >= 0:
                    count += len(CD)
                ab_ptr +=1
                continue
            # Check if ab is positive or negative
            if ab > 0:
                max_cd = mid // ab
                # Check if mid and ab have same sign; if not, division floors to negative infinity
                if (mid < 0) and (mid % ab != 0):
                    max_cd -=1
                cnt = bisect.bisect_right(cd_values, max_cd)
                count += cnt
            else:
                # ab <0
                q, r = divmod(mid, ab)
                if r !=0:
                    q +=1
                cnt = len(cd_values) - bisect.bisect_left(cd_values, q)
                count += cnt
            ab_ptr +=1
        # Binary search step
        if count >= S:
            T = mid
            right = mid -1
        else:
            left = mid +1
    
    print(T)
    # Now find a, b, c, d such that a*b*c*d = T
    found = False
    # Iterate through AB to find a*b
    for ab in AB:
        a_b_val, a_val, b_val = ab
        if a_b_val ==0:
            if T !=0:
                continue
            # T must be zero. Look for any cd with zero in CD
            # Find if CD has zero
            zero_pos = bisect.bisect_left(cd_values, 0)
            if zero_pos < len(cd_values) and cd_values[zero_pos] ==0:
                # Get the first occurrence
                cd = CD[zero_pos]
                c_val, d_val = cd[1], cd[2]
                print(f"{a_val} {b_val} {c_val} {d_val}")
                found = True
                break
        else:
            if T % a_b_val !=0:
                continue
            required_cd = T // a_b_val
            # Find if required_cd exists in CD
            pos = bisect.bisect_left(cd_values, required_cd)
            if pos < len(cd_values) and cd_values[pos] == required_cd:
                # Get the first occurrence
                cd = CD[pos]
                c_val, d_val = cd[1], cd[2]
                print(f"{a_val} {b_val} {c_val} {d_val}")
                found = True
                break
        if found:
            break
    
    if not found:
        # This should not happen as per problem statement
        pass

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