結果

問題 No.2740 Old Maid
コンテスト
ユーザー detteiuu
提出日時 2024-04-24 22:05:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 562 ms / 2,000 ms
コード長 754 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 148,596 KB
最終ジャッジ日時 2024-11-07 07:17:06
合計ジャッジ時間 21,392 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from heapq import heappush, heappop, heapify

N = int(input())
P = list(map(int, input().split()))

pre = dict()
nex = dict()
for i in range(N):
    if i == 0:
        pre[P[i]] = -1
    else:
        pre[P[i]] = P[i-1]
    if i == N-1:
        nex[P[i]] = -1
    else:
        nex[P[i]] = P[i+1]

que = P[:N-1]
heapify(que)
ans = []
S = set()
while que:
    n = heappop(que)
    if n in S:
        continue
    ans.append(n)
    ans.append(nex[n])
    S.add(n)
    S.add(nex[n])
    if nex[nex[n]] == -1:
        if pre[n] != -1:
            S.add(pre[n])
        nex[pre[n]] = -1
    else:
        nex[pre[n]] = nex[nex[n]]
        pre[nex[nex[n]]] = pre[n]
    pre.pop(n)
    pre.pop(nex[n])
    ne = nex[n]
    nex.pop(n)
    nex.pop(ne)

print(*ans)
0