結果

問題 No.1604 Swap Sort:ONE
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:52:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 71 ms / 2,000 ms
コード長 1,321 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 81,988 KB
実行使用メモリ 74,696 KB
最終ジャッジ日時 2025-03-26 15:53:35
合計ジャッジ時間 2,989 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
P = list(map(int, input().split()))

sorted_values = sorted(P)
groups = []

if sorted_values:
    current_group = [sorted_values[0]]
    for i in range(1, len(sorted_values)):
        if sorted_values[i] == sorted_values[i-1] + 1:
            current_group.append(sorted_values[i])
        else:
            groups.append(current_group)
            current_group = [sorted_values[i]]
    groups.append(current_group)

total_inversions = 0

def count_inversions(arr):
    if len(arr) <= 1:
        return 0
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    inversions = count_inversions(left) + count_inversions(right)
    
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
            inversions += len(left) - i
        k += 1
    
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1
    
    return inversions

for group in groups:
    min_v = group[0]
    max_v = group[-1]
    subarray = [P[i - 1] for i in range(min_v, max_v + 1)]
    total_inversions += count_inversions(subarray.copy())

print(total_inversions)
0