結果

問題 No.1687 What the Heck?
ユーザー lam6er
提出日時 2025-04-15 21:07:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,412 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,476 KB
実行使用メモリ 124,580 KB
最終ジャッジ日時 2025-04-15 21:13:42
合計ジャッジ時間 3,729 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #

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