結果

問題 No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:21:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,468 bytes
記録
コンパイル時間 192 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 129,076 KB
最終ジャッジ日時 2025-06-12 18:21:49
合計ジャッジ時間 11,325 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 8 TLE * 1 -- * 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_pairs and CD_pairs
AB_pairs = []
for a in A:
    for b in B:
        AB_pairs.append((a * b, a, b))
AB_pairs.sort(key=lambda x: x[0])
AB_list = [x[0] for x in AB_pairs]

CD_pairs = []
for c in C:
    for d in D:
        CD_pairs.append((c * d, c, d))
CD_pairs.sort(key=lambda x: x[0])
CD_list = [x[0] for x in CD_pairs]

def count(X):
    total = 0
    for ab in AB_list:
        if ab == 0:
            if X >= 0:
                total += len(CD_list)
            continue
        if ab > 0:
            max_cd = X / ab
            cnt = bisect.bisect_right(CD_list, max_cd)
            total += cnt
        else:
            min_cd = X / ab
            cnt = len(CD_list) - bisect.bisect_left(CD_list, min_cd)
            total += cnt
    return total

# Determine the search range
ab_min = AB_list[0]
ab_max = AB_list[-1]
cd_min = CD_list[0]
cd_max = CD_list[-1]

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
answer = None
while low <= high:
    mid = (low + high) // 2
    c = count(mid)
    if c >= S:
        high = mid - 1
        answer = mid
    else:
        low = mid + 1

T = low if answer is None else answer

# Find the elements a, b, c, d
found = False

# Check for T=0 case
if T == 0:
    for ab_product, a, b in AB_pairs:
        if ab_product == 0:
            # Any CD pair will work
            cd_product, c, d = CD_pairs[0]
            print(0)
            print(a, b, c, d)
            found = True
            break
    if not found:
        for cd_product, c, d in CD_pairs:
            if cd_product == 0:
                # Any AB pair will work
                ab_product, a, b = AB_pairs[0]
                print(0)
                print(a, b, c, d)
                found = True
                break
else:
    # T is non-zero
    for ab_product, a, b in AB_pairs:
        if ab_product == 0:
            continue
        if T % ab_product != 0:
            continue
        target_cd = T // ab_product
        idx = bisect.bisect_left(CD_list, target_cd)
        if idx < len(CD_list) and CD_list[idx] == target_cd:
            # Find the first occurrence of target_cd in CD_pairs
            for i in range(idx, len(CD_pairs)):
                if CD_pairs[i][0] == target_cd:
                    c, d = CD_pairs[i][1], CD_pairs[i][2]
                    print(T)
                    print(a, b, c, d)
                    found = True
                    break
            if found:
                break

if not found:
    # Fallback: check CD_pairs in reverse (in case of negative products)
    for cd_product, c, d in CD_pairs:
        if cd_product == 0:
            continue
        if T % cd_product != 0:
            continue
        target_ab = T // cd_product
        idx = bisect.bisect_left(AB_list, target_ab)
        if idx < len(AB_list) and AB_list[idx] == target_ab:
            for i in range(idx, len(AB_pairs)):
                if AB_pairs[i][0] == target_ab:
                    a, b = AB_pairs[i][1], AB_pairs[i][2]
                    print(T)
                    print(a, b, c, d)
                    found = True
                    break
            if found:
                break
0