結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 2025-06-12 18:23:56 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,562 bytes |
コンパイル時間 | 213 ms |
コンパイル使用メモリ | 82,600 KB |
実行使用メモリ | 130,472 KB |
最終ジャッジ日時 | 2025-06-12 18:24:28 |
合計ジャッジ時間 | 10,479 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 TLE * 4 -- * 42 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read().split() idx = 0 K = int(input[idx]); idx +=1 L = int(input[idx]); idx +=1 M = int(input[idx]); idx +=1 N = int(input[idx]); idx +=1 S = int(input[idx]); idx +=1 A = list(map(int, input[idx:idx+K])) idx += K B = list(map(int, input[idx:idx+L])) idx += L C = list(map(int, input[idx:idx+M])) idx += M D = list(map(int, input[idx:idx+N])) idx += N # Generate AB pairs (product, a_idx, b_idx) AB = [] for a_idx in range(K): a = A[a_idx] for b_idx in range(L): b = B[b_idx] prod = a * b AB.append((prod, a_idx, b_idx)) # Sort AB by product AB.sort() # Generate CD pairs (product, c_idx, d_idx) CD = [] for c_idx in range(M): c = C[c_idx] for d_idx in range(N): d = D[d_idx] prod = c * d CD.append((prod, c_idx, d_idx)) # Sort CD by product CD.sort() # Extract products for binary search AB_products = [x[0] for x in AB] CD_products = [x[0] for x in CD] # Function to count the number of elements <= X def count_le(X): count = 0 # Iterate through each AB product for p in AB_products: if p == 0: if X >= 0: count += len(CD_products) continue # Find the number of CD products q where p*q <= X if p > 0: max_q = X // p if p * max_q > X: max_q -= 1 # Find the rightmost q <= max_q cnt = bisect.bisect_right(CD_products, max_q) count += cnt else: # p < 0: q >= X/p (since p is negative, division flips inequality) min_q = X // p if X % p != 0: min_q += 1 # Find the first q >= min_q cnt = len(CD_products) - bisect.bisect_left(CD_products, min_q) count += cnt return count # Binary search for the smallest X where count_le(X) >= S low = -10**18 high = 10**18 answer = None while low <= high: mid = (low + high) // 2 cnt = count_le(mid) if cnt >= S: answer = mid high = mid - 1 else: low = mid + 1 T = answer # Now find a combination that produces T found = False a_ans = b_ans = c_ans = d_ans = None # Check AB and CD pairs for p, a_idx, b_idx in AB: if p == 0: if T == 0: # Any CD pair will do if CD: c_val, c_idx_cd, d_idx_cd = CD[0] a_ans = A[a_idx] b_ans = B[b_idx] c_ans = C[c_idx_cd] d_ans = D[d_idx_cd] found = True break continue if T % p != 0: continue target_q = T // p # Search in CD_products idx_q = bisect.bisect_left(CD_products, target_q) if idx_q < len(CD_products) and CD_products[idx_q] == target_q: # Find any occurrence while idx_q < len(CD_products) and CD_products[idx_q] == target_q: c_val, c_idx_cd, d_idx_cd = CD[idx_q] a_ans = A[a_idx] b_ans = B[b_idx] c_ans = C[c_idx_cd] d_ans = D[d_idx_cd] found = True break if found: break if not found: # Check if T is zero and there are zero in CD if T == 0: # Check if any CD is zero for q, c_idx_cd, d_idx_cd in CD: if q == 0: # Find any AB with any p a_ans = A[0] b_ans = B[0] c_ans = C[c_idx_cd] d_ans = D[d_idx_cd] found = True break if not found: # Check if any AB is zero for p, a_idx, b_idx in AB: if p == 0: # Any CD c_ans = C[0] d_ans = D[0] a_ans = A[a_idx] b_ans = B[b_idx] found = True break print(T) print(a_ans, b_ans, c_ans, d_ans) if __name__ == '__main__': main()