結果
問題 |
No.1687 What the Heck?
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:52:53 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,557 bytes |
コンパイル時間 | 152 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 124,888 KB |
最終ジャッジ日時 | 2025-03-20 20:53:07 |
合計ジャッジ時間 | 5,541 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 WA * 10 |
ソースコード
def main(): import sys input = sys.stdin.read data = input().split() n = int(data[0]) p = list(map(int, data[1:n+1])) rounds = [(i + 1, p[i]) for i in range(n)] rounds.sort(reverse=True, key=lambda x: x[0]) max_n = n + 2 # To handle up to N+1 # Union-Find structures for next and previous available cards next_parent = list(range(max_n + 1)) prev_parent = list(range(max_n + 1)) def find_next(x): if next_parent[x] != x: next_parent[x] = find_next(next_parent[x]) return next_parent[x] def find_prev(x): if prev_parent[x] != x: prev_parent[x] = find_prev(prev_parent[x]) return prev_parent[x] score = 0 for i, pi in rounds: target = pi + 1 x = find_next(target) if x <= n: score += i # Update next_parent to point to the next available card next_parent[x] = find_next(x + 1) # Update prev_parent to point to the previous available card prev_parent[x] = find_prev(x - 1) else: # Find the largest available card y = find_prev(n) if y >= 1: if y < pi: score -= i elif y > pi: score += i # Update the unions for the used card y next_parent[y] = find_next(y + 1) prev_parent[y] = find_prev(y - 1) print(score) if __name__ == "__main__": main()