結果

問題 No.2453 Seat Allocation
ユーザー rlangevinrlangevin
提出日時 2023-09-01 22:54:26
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,110 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 111,524 KB
最終ジャッジ日時 2025-01-03 10:47:52
合計ジャッジ時間 8,199 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 17 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from math import *
class RationalHeap:
def __init__(self):
self.H = []
def add(self, A, B, n, ind):
g = gcd(A, B)
A //= g
B //= g
self.H.append((A, B, n, ind))
now = len(self.H) - 1
while 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 = now
else:
break
return
def pop(self):
ra, rb, rn, ri = self.H[0]
a, b, n, i = self.H.pop()
self.H[0] = (a, b, n, i)
now = 0
while True:
if len(self.H) < 2 * now + 2:
break
ch1 = 2 * now + 1
if len(self.H) < 2 * now + 3:
if self.check(ch1, now):
self.H[now], self.H[ch1] = self.H[ch1], self.H[now]
now = ch1
else:
break
else:
ch2 = 2 * now + 2
if self.check(ch1, ch2):
ch = ch1
else:
ch = ch2
if self.check(ch, now):
self.H[now], self.H[ch] = self.H[ch], self.H[now]
now = ch
else:
break
return rn, ri
def 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 True
else:
return False
else:
if a1 * b2 > b1 * a2:
return True
else:
return False
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0