結果

問題 No.1687 What the Heck?
コンテスト
ユーザー lam6er
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0