結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 2025-04-16 16:45:33 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,009 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 80,500 KB |
最終ジャッジ日時 | 2025-04-16 16:46:50 |
合計ジャッジ時間 | 10,903 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 TLE * 1 -- * 45 |
ソースコード
import bisect 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 array AB = [] for w in range(K): a = A[w] for x in range(L): b = B[x] ab = a * b AB.append((ab, w, x)) # Generate CD array CD = [] for y in range(M): c = C[y] for z in range(N): d = D[z] cd = c * d CD.append((cd, y, z)) # Sort AB and CD by their product values AB.sort(key=lambda t: t[0]) CD.sort(key=lambda t: t[0]) CD_values = [t[0] for t in CD] # Compute initial low and high for binary search if not AB or not CD: print(0) print(0, 0, 0, 0) return ab_min = AB[0][0] ab_max = AB[-1][0] cd_min = CD[0][0] cd_max = CD[-1][0] candidates = [ ab_min * cd_min, ab_min * cd_max, ab_max * cd_min, ab_max * cd_max ] low = min(candidates) high = max(candidates) # Binary search to find T T = 0 while low <= high: mid = (low + high) // 2 # Calculate how many elements <= mid cnt = 0 for ab, w, x in AB: if ab == 0: if mid >= 0: cnt += len(CD) continue target = mid // ab rem = mid % ab if ab > 0: # CD[j] <= target pos = bisect.bisect_right(CD_values, target) cnt += pos else: # ab <0, CD[j] >= ceil(mid/ab) if rem == 0: ceil_val = target else: ceil_val = target + 1 pos = bisect.bisect_left(CD_values, ceil_val) cnt += len(CD_values) - pos if cnt >= S: T = mid high = mid - 1 else: low = mid + 1 # Now find a combination a,b,c,d such that a*b*c*d = T a = b = c = d = None found = False # Check AB and CD for ab_val, w, x in AB: if ab_val == 0: if T == 0: # Any CD element will do cd_val, y, z = CD[0] a = A[w] b = B[x] c = C[y] d = D[z] found = True break else: continue if T % ab_val != 0: continue required_cd = T // ab_val # Find in CD pos = bisect.bisect_left(CD_values, required_cd) if pos < len(CD_values) and CD_values[pos] == required_cd: # Check all possible positions (might have duplicates) # Take the first occurrence cd_val, y, z = CD[pos] a = A[w] b = B[x] c = C[y] d = D[z] found = True break if not found and T == 0: # Check if any AB is zero and CD is any for ab_val, w, x in AB: if ab_val == 0: cd_val, y, z = CD[0] a = A[w] b = B[x] c = C[y] d = D[z] found = True break if not found: # Check if any CD is zero for cd_val, y, z in CD: if cd_val == 0: ab_val, w, x = AB[0] a = A[w] b = B[x] c = C[y] d = D[z] found = True break print(T) print(a, b, c, d) if __name__ == '__main__': main()