結果

問題 No.1816 MUL-DIV Game
ユーザー gew1fw
提出日時 2025-06-12 12:47:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,410 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 268,420 KB
最終ジャッジ日時 2025-06-12 12:47:41
合計ジャッジ時間 9,049 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = list(map(int, input().split()))
    N = data[0]
    A = data[1:N+1]
    
    if N == 1:
        print(A[0])
        return
    
    total_steps = N - 1
    alice_steps = (total_steps + 1) // 2
    bob_steps = total_steps // 2
    
    if bob_steps == 0:
        product = 1
        for num in A:
            product *= num
        print(product)
        return
    
    # Min heap for Alice's operations (merge two smallest)
    min_heap = A.copy()
    heapq.heapify(min_heap)
    
    # Max heap for Bob's operations (merge two largest)
    max_heap = [-x for x in A]
    heapq.heapify(max_heap)
    
    # We need to track the current elements. However, using heaps directly may not work due to duplicates.
    # Instead, we can use a list and keep it sorted, but for large N this is not feasible.
    # Alternative approach: use a list to keep track of elements, but this is not efficient for large N.
    # For the purpose of this problem, we'll proceed with the heaps, acknowledging potential inaccuracies.
    
    # Lists to collect the largest pairs for Bob
    bob_pairs_product = 1
    
    # We need to alternate between Alice and Bob steps
    current_min_heap = list(A)
    heapq.heapify(current_min_heap)
    
    current_max_heap = []
    for num in current_min_heap:
        heapq.heappush(current_max_heap, -num)
    
    for step in range(total_steps):
        if step % 2 == 0:  # Alice's turn
            if len(current_min_heap) < 2:
                break
            a = heapq.heappop(current_min_heap)
            b = heapq.heappop(current_min_heap)
            product = a * b
            heapq.heappush(current_min_heap, product)
            heapq.heappush(current_max_heap, -product)
        else:  # Bob's turn
            if len(current_max_heap) < 2:
                break
            a = -heapq.heappop(current_max_heap)
            b = -heapq.heappop(current_max_heap)
            if a < b:
                a, b = b, a
            bob_pairs_product *= a * b
            new_val = 1
            heapq.heappush(current_max_heap, -new_val)
            heapq.heappush(current_min_heap, new_val)
    
    # Compute initial product
    initial_product = 1
    for num in data[1:N+1]:
        initial_product *= num
    
    print(initial_product // bob_pairs_product)

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