結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:19:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,468 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 127,920 KB |
最終ジャッジ日時 | 2025-06-12 13:21:55 |
合計ジャッジ時間 | 12,105 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 8 TLE * 1 -- * 45 |
ソースコード
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