結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:42:59 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,408 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 162,680 KB |
最終ジャッジ日時 | 2025-06-12 21:46:52 |
合計ジャッジ時間 | 10,362 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 WA * 1 TLE * 1 -- * 45 |
ソースコード
import bisect 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 # Compute AB and CD AB = [] for i in range(K): a = A[i] for j in range(L): b = B[j] AB.append((a * b, i, j)) AB.sort(key=lambda x: x[0]) CD = [] for k in range(M): c = C[k] for l in range(N): d = D[l] CD.append((c * d, k, l)) CD.sort(key=lambda x: x[0]) # Build CD dictionary and values list cd_dict = defaultdict(list) cd_values = [] for val, k, l in CD: cd_dict[val].append((k, l)) cd_values.append(val) # Binary search to find T if not AB or not CD: print(0) print(*([0]*4)) return min_ab = AB[0][0] max_ab = AB[-1][0] min_cd = CD[0][0] max_cd = CD[-1][0] candidates = [min_ab * min_cd, min_ab * max_cd, max_ab * min_cd, max_ab * max_cd] low = min(candidates) high = max(candidates) while low < high: mid = (low + high) // 2 count = 0 for ab_tuple in AB: ab_val = ab_tuple[0] if ab_val == 0: if mid >= 0: count += len(CD) continue if ab_val > 0: target = mid // ab_val cnt = bisect.bisect_right(cd_values, target) count += cnt else: target = mid / ab_val idx = bisect.bisect_left(cd_values, target) count += len(cd_values) - idx if count >= S: high = mid else: low = mid + 1 T = low # Find a, b, c, d for ab_tuple in AB: ab_val, i, j = ab_tuple if ab_val == 0: if T != 0: continue # T is 0 # Find a and b such that a*b ==0 a = None b = None # Check A for a_val in A: if a_val == 0: a = a_val b = B[j] break if a is None: # Check B for b_val in B: if b_val == 0: b = b_val a = A[i] break # Choose first element in CD cd_tuple = CD[0] c = C[cd_tuple[1]] d = D[cd_tuple[2]] print(T) print(a, b, c, d) return else: if T % ab_val != 0: continue target = T // ab_val if target in cd_dict: k, l = cd_dict[target][0] a = A[i] b = B[j] c = C[k] d = D[l] print(T) print(a, b, c, d) return # Fallback in case nothing found (should not happen) print(0) print(0, 0, 0, 0) if __name__ == "__main__": main()