結果

問題 No.1604 Swap Sort:ONE
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:50:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 97 ms / 2,000 ms
コード長 1,600 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 67,464 KB
最終ジャッジ日時 2025-03-31 17:51:06
合計ジャッジ時間 3,111 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

sorted_values = sorted(P)

# Split into blocks of consecutive values
blocks = []
if sorted_values:
    current_min = sorted_values[0]
    current_max = sorted_values[0]
    for v in sorted_values[1:]:
        if v == current_max + 1:
            current_max = v
        else:
            blocks.append((current_min, current_max))
            current_min = v
            current_max = v
    blocks.append((current_min, current_max))

# Create a list of blocks sorted by their minimum values
sorted_blocks = sorted(blocks, key=lambda x: x[0])

# Map each value to its corresponding block index in sorted_blocks
value_to_block = {}
block_index = 0
for (min_val, max_val) in sorted_blocks:
    for v in range(min_val, max_val + 1):
        value_to_block[v] = block_index
    block_index += 1

# Check if the blocks in the original permutation are in the correct order
current_block_order = [value_to_block[v] for v in P]
prev_block = -1
for block_idx in current_block_order:
    if block_idx < prev_block:
        print(-1)
        exit()
    prev_block = block_idx

# Group elements by their block
block_elements = [[] for _ in range(len(sorted_blocks))]
for v in P:
    block_idx = value_to_block[v]
    block_elements[block_idx].append(v)

# Calculate total inversions in each block
total_inversions = 0
for elements in block_elements:
    m = len(elements)
    inv = 0
    for i in range(m):
        for j in range(i + 1, m):
            if elements[i] > elements[j]:
                inv += 1
    total_inversions += inv

print(total_inversions)
0