結果

問題 No.1687 What the Heck?
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:47:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,310 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 135,504 KB
最終ジャッジ日時 2025-03-31 17:49:07
合計ジャッジ時間 2,801 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    P = list(map(int, input[idx:idx+N]))
    idx += N

    # Create rounds as tuples of (P_i, i), 1-based
    rounds = []
    for i in range(N):
        rounds.append((P[i], i + 1))  # i+1 is the round number (1-based)

    # Sort rounds in descending order of the round number (i)
    rounds.sort(key=lambda x: -x[1])

    # Initialize DSU parent array: 0 to N+2 (to handle up to N+1)
    parent = list(range(N + 2 + 1))  # indices 0..N+1 (inclusive)

    def find(a):
        # Path compression
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a

    total = 0
    for p, i in rounds:
        # Check for a > p
        candidate = find(p + 1)
        if candidate <= N:
            total += i
            parent[candidate] = find(candidate + 1)
        else:
            # Check for a == p
            candidate = find(p)
            if candidate == p:
                parent[p] = find(p + 1)
            else:
                # Take the smallest available
                candidate = find(1)
                total -= i
                parent[candidate] = find(candidate + 1)
    print(total)

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