結果
問題 |
No.1687 What the Heck?
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:25:24 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,412 bytes |
コンパイル時間 | 542 ms |
コンパイル使用メモリ | 82,080 KB |
実行使用メモリ | 124,724 KB |
最終ジャッジ日時 | 2025-04-16 15:27:05 |
合計ジャッジ時間 | 3,618 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 WA * 11 |
ソースコード
import bisect 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(key=lambda x: -x[0]) # Sort by descending round index T = list(range(1, n + 1)) parent = list(range(n)) def find(u): while parent[u] != u: parent[u] = parent[parent[u]] # Path compression u = parent[u] return u ans = 0 for i, current_p in rounds: pos = bisect.bisect_right(T, current_p) if pos < n: idx = find(pos) if idx < n: ans += i parent[idx] = idx + 1 else: idx = find(0) if idx < n: if T[idx] < current_p: ans -= i elif T[idx] == current_p: pass else: ans += i parent[idx] = idx + 1 else: idx = find(0) if idx < n: if T[idx] < current_p: ans -= i elif T[idx] == current_p: pass else: ans += i parent[idx] = idx + 1 print(ans) if __name__ == "__main__": main()