結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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