結果
問題 |
No.1361 [Zelkova 4th Tune *] QUADRUPLE-SEQUENCEの詩
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:37:41 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,390 bytes |
コンパイル時間 | 185 ms |
コンパイル使用メモリ | 81,848 KB |
実行使用メモリ | 145,268 KB |
最終ジャッジ日時 | 2025-06-12 21:40:45 |
合計ジャッジ時間 | 11,867 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 WA * 8 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 # Compute AB AB = [] for w in range(K): a = A[w] for x in range(L): b = B[x] ab_product = a * b AB.append( (ab_product, w, x) ) AB.sort() AB_products = [ab[0] for ab in AB] # Compute CD CD = [] for y in range(M): c = C[y] for z in range(N): d = D[z] cd_product = c * d CD.append( (cd_product, y, z) ) CD.sort() CD_products = [cd[0] for cd in CD] # Binary search for T # Compute possible min and max min_ab = AB_products[0] if AB else 0 max_ab = AB_products[-1] if AB else 0 min_cd = CD_products[0] if CD else 0 max_cd = CD_products[-1] if CD else 0 possible_products = [ min_ab * min_cd, min_ab * max_cd, max_ab * min_cd, max_ab * max_cd ] low = min(possible_products) high = max(possible_products) # Binary search left = low right = high def count_less_equal(T): cnt = 0 for ab in AB: a = ab[0] if a == 0: if T >= 0: cnt += len(CD) continue # Compute target target = T / a # Check if target makes sense if a > 0: if CD_products[-1] < target: cnt += len(CD) continue if CD_products[0] > target: continue idx = bisect.bisect_right(CD_products, target) cnt += idx else: if CD_products[0] > target: cnt += len(CD) continue if CD_products[-1] < target: continue idx = bisect.bisect_left(CD_products, target) cnt += len(CD_products) - idx return cnt while left < right: mid = (left + right) // 2 cnt = count_less_equal(mid) if cnt < S: left = mid + 1 else: right = mid T = left # Now find a and c # Precompute CD's product to (y, z) map cd_dict = {} for c in CD: p = c[0] if p not in cd_dict: cd_dict[p] = [] cd_dict[p].append( (c[1], c[2]) ) for ab in AB: a = ab[0] if a == 0: if T == 0: # find any c with product 0 if 0 in cd_dict: c_y, c_z = cd_dict[0][0] print(T) print(A[ab[1]], B[ab[2]], C[c_y], D[c_z]) return continue if T % a != 0: continue target = T // a if target in cd_dict: c_y, c_z = cd_dict[target][0] print(T) print(A[ab[1]], B[ab[2]], C[c_y], D[c_z]) return if __name__ == '__main__': main()