結果

問題 No.2453 Seat Allocation
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:23:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 348 ms / 2,000 ms
コード長 1,342 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 121,104 KB
最終ジャッジ日時 2025-06-20 02:27:48
合計ジャッジ時間 5,907 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

class Candidate:
    def __init__(self, a, b, party, j):
        self.a = a
        self.b = b
        self.party = party
        self.j = j

    def __lt__(self, other):
        val1 = self.a * other.b
        val2 = other.a * self.b
        if val1 > val2:
            return True
        elif val1 < val2:
            return False
        else:
            return self.party < other.party

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, M = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    A_list = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+M]))
    ptr += M

    # Initialize A as 1-based array
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = A_list[i - 1]

    heap = []
    # Push initial candidates (j=1 for each party)
    for party in range(1, N + 1):
        a = A[party]
        b = B[0]
        heapq.heappush(heap, Candidate(a, b, party, 1))

    # Process M elections
    for _ in range(M):
        current = heapq.heappop(heap)
        print(current.party)
        j_next = current.j + 1
        if j_next <= M:
            next_b = B[j_next - 1]
            next_candidate = Candidate(current.a, next_b, current.party, j_next)
            heapq.heappush(heap, next_candidate)

if __name__ == '__main__':
    main()
0