結果
問題 |
No.2740 Old Maid
|
ユーザー |
|
提出日時 | 2025-10-04 01:54:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 976 ms / 2,000 ms |
コード長 | 1,357 bytes |
コンパイル時間 | 364 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 185,772 KB |
最終ジャッジ日時 | 2025-10-04 01:54:46 |
合計ジャッジ時間 | 31,055 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
## https://yukicoder.me/problems/no/2740 import heapq def main(): N = int(input()) P = list(map(int, input().split())) # 双方向リスト準備 p_map = {} for i in range(N): node = { "value": P[i], "prev" : None, "next": None } p_map[P[i]] = node if i > 0: p1 = P[i - 1] p_node = p_map[p1] p_node["next"] = node node["prev"] = p_node queue = [] for i in range(N - 1): p1 = P[i] p2 = P[i + 1] heapq.heappush(queue, (p1, p2)) used = [False] * N answer = [] while len(queue) > 0: p1, p2 = heapq.heappop(queue) if not used[p1 - 1] and not used[p2 - 1]: answer.append(p1) answer.append(p2) used[p1 - 1] = True used[p2 - 1] = True p_node = p_map[p1]["prev"] n_node = p_map[p2]["next"] if p_node is not None: p_node["next"] = n_node if n_node is not None: n_node["prev"] = p_node if p_node is not None and n_node is not None: heapq.heappush(queue, (p_node["value"], n_node["value"])) print(" ".join(map(str, answer))) if __name__ == "__main__": main()