結果
問題 | No.2453 Seat Allocation |
ユーザー |
![]() |
提出日時 | 2023-09-01 22:55:55 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,123 bytes |
コンパイル時間 | 377 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 112,128 KB |
最終ジャッジ日時 | 2025-01-03 10:50:21 |
合計ジャッジ時間 | 8,300 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 WA * 17 |
ソースコード
from math import *class RationalHeap:def __init__(self):self.H = []def add(self, A, B, n, ind):g = gcd(A, B)A //= gB //= gself.H.append((A, B, n, ind))now = len(self.H) - 1while now:par = (now - 1) // 2# print("add", now, par, self.H)if self.check(now, par):self.H[now], self.H[par] = self.H[par], self.H[now]par = nowelse:breakreturndef pop(self):ra, rb, rn, ri = self.H[0]a, b, n, i = self.H.pop()self.H[0] = (a, b, n, i)now = 0while True:if len(self.H) < 2 * now + 2:breakch1 = 2 * now + 1if len(self.H) < 2 * now + 3:if self.check(ch1, now):self.H[now], self.H[ch1] = self.H[ch1], self.H[now]now = ch1else:breakelse:ch2 = 2 * now + 2if self.check(ch1, ch2):ch = ch1else:ch = ch2if self.check(ch, now):self.H[now], self.H[ch] = self.H[ch], self.H[now]now = chelse:breakreturn rn, ridef check(self, p, q):# print("test", p, q)a1, b1, n1, i1 = self.H[p]a2, b2, n2, i2 = self.H[q]if a1 == a2 and b1 == b2:if n1 < n2:return Trueelse:return Falseelse:if a1 * b2 > b1 * a2:return Trueelse:return FalseN, M = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split())) + [10 ** 18]H = RationalHeap()for i in range(N):H.add(A[i], B[0], i, 0)for _ in range(M):n, i = H.pop()print(n + 1)H.add(A[n], B[i + 1], n, i + 1)