結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:50:35 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,453 bytes |
コンパイル時間 | 351 ms |
コンパイル使用メモリ | 82,900 KB |
実行使用メモリ | 81,432 KB |
最終ジャッジ日時 | 2025-03-31 17:51:34 |
合計ジャッジ時間 | 12,582 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 WA * 11 TLE * 1 -- * 45 |
ソースコード
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 and CD arrays AB = [] for a in A: for b in B: AB.append( (a*b, a, b) ) AB.sort(key=lambda x: x[0]) ab_values = [x[0] for x in AB] CD = [] for c in C: for d in D: CD.append( (c*d, c, d) ) CD.sort(key=lambda x: x[0]) cd_values = [x[0] for x in CD] # Binary search for T left = -10**18 right = 10**18 T = 0 while left <= right: mid = (left + right) // 2 count = 0 # Iterate through all AB and calculate CD's allowed range ab_ptr = 0 while ab_ptr < len(AB): ab = AB[ab_ptr][0] # Handle zero case if ab == 0: if mid >= 0: count += len(CD) ab_ptr +=1 continue # Check if ab is positive or negative if ab > 0: max_cd = mid // ab # Check if mid and ab have same sign; if not, division floors to negative infinity if (mid < 0) and (mid % ab != 0): max_cd -=1 cnt = bisect.bisect_right(cd_values, max_cd) count += cnt else: # ab <0 q, r = divmod(mid, ab) if r !=0: q +=1 cnt = len(cd_values) - bisect.bisect_left(cd_values, q) count += cnt ab_ptr +=1 # Binary search step if count >= S: T = mid right = mid -1 else: left = mid +1 print(T) # Now find a, b, c, d such that a*b*c*d = T found = False # Iterate through AB to find a*b for ab in AB: a_b_val, a_val, b_val = ab if a_b_val ==0: if T !=0: continue # T must be zero. Look for any cd with zero in CD # Find if CD has zero zero_pos = bisect.bisect_left(cd_values, 0) if zero_pos < len(cd_values) and cd_values[zero_pos] ==0: # Get the first occurrence cd = CD[zero_pos] c_val, d_val = cd[1], cd[2] print(f"{a_val} {b_val} {c_val} {d_val}") found = True break else: if T % a_b_val !=0: continue required_cd = T // a_b_val # Find if required_cd exists in CD pos = bisect.bisect_left(cd_values, required_cd) if pos < len(cd_values) and cd_values[pos] == required_cd: # Get the first occurrence cd = CD[pos] c_val, d_val = cd[1], cd[2] print(f"{a_val} {b_val} {c_val} {d_val}") found = True break if found: break if not found: # This should not happen as per problem statement pass if __name__ == "__main__": main()