結果
問題 |
No.1687 What the Heck?
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()