結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:22:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,638 bytes
記録
コンパイル時間 219 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 129,528 KB
最終ジャッジ日時 2025-06-12 18:22:50
合計ジャッジ時間 22,947 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26 TLE * 3 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect

K, L, M, N, S = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))

# Generate AB products along with their elements
ab_list = []
for a in A:
    for b in B:
        product = a * b
        ab_list.append((product, a, b))

ab_list.sort(key=lambda x: x[0])
ab_products = [x[0] for x in ab_list]
ab_values = ab_list  # list of tuples (product, a, b)

# Generate CD products along with their elements
cd_list = []
for c in C:
    for d in D:
        product = c * d
        cd_list.append((product, c, d))

cd_list.sort(key=lambda x: x[0])
cd_products = [x[0] for x in cd_list]
cd_values = cd_list  # list of tuples (product, c, d)

# Binary search to find T
low = -10**60
high = 10**60
answer = None

while low <= high:
    mid = (low + high) // 2
    count = 0
    for ab in ab_products:
        if ab > 0:
            max_cd = mid // ab
            cnt = bisect.bisect_right(cd_products, max_cd)
            count += cnt
        elif ab == 0:
            if mid >= 0:
                count += len(cd_products)
        else:
            threshold = (mid + ab + 1) // ab
            idx = bisect.bisect_left(cd_products, threshold)
            cnt = len(cd_products) - idx
            count += cnt
    if count >= S:
        answer = mid
        high = mid - 1
    else:
        low = mid + 1

T = answer

# Find corresponding elements
found = False
for ab_tuple in ab_values:
    ab_val, a_val, b_val = ab_tuple
    if ab_val == 0:
        if T == 0:
            cd_tuple = cd_values[0]
            c_val, d_val = cd_tuple[1], cd_tuple[2]
            print(T)
            print(a_val, b_val, c_val, d_val)
            found = True
            break
        else:
            continue
    else:
        if T % ab_val != 0:
            continue
        cd_candidate = T // ab_val
        idx = bisect.bisect_left(cd_products, cd_candidate)
        if idx < len(cd_products) and cd_products[idx] == cd_candidate:
            cd_tuple = cd_values[idx]
            c_val, d_val = cd_tuple[1], cd_tuple[2]
            print(T)
            print(a_val, b_val, c_val, d_val)
            found = True
            break

if not found and T == 0:
    for ab_tuple in ab_values:
        ab_val, a_val, b_val = ab_tuple
        if ab_val == 0:
            cd_tuple = cd_values[0]
            c_val, d_val = cd_tuple[1], cd_tuple[2]
            print(T)
            print(a_val, b_val, c_val, d_val)
            found = True
            break

if not found:
    print("Error")  # This should theoretically never happen
0