結果
問題 |
No.1604 Swap Sort:ONE
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)