結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:21:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,214 bytes |
コンパイル時間 | 144 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 131,984 KB |
最終ジャッジ日時 | 2025-06-12 18:22:23 |
合計ジャッジ時間 | 10,895 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 WA * 5 TLE * 1 -- * 45 |
ソースコード
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()