結果

問題 No.366 ロボットソート
ユーザー lam6er
提出日時 2025-03-20 20:58:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 1,909 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,564 KB
実行使用メモリ 61,824 KB
最終ジャッジ日時 2025-03-20 20:59:39
合計ジャッジ時間 1,846 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # Adding +2 to avoid overflow issues

    def update(self, index, delta=1):
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def query(self, index):
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= index & -index
        return res

def count_inversion(arr):
    m = len(arr)
    if m == 0:
        return 0
    ft = FenwickTree(m)
    ans = 0
    for x in reversed(arr):
        ans += ft.query(x)
        ft.update(x + 1)
    return ans

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, K = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    a = list(map(int, input[ptr:ptr+N]))
    ptr += N
    sorted_a = sorted(a)
    value_to_pos = {val: idx for idx, val in enumerate(sorted_a)}
    
    possible = True
    for idx in range(N):
        original_pos = idx + 1  # 1-based
        x = a[idx]
        target_pos = value_to_pos[x] + 1  # 1-based
        if (original_pos - 1) % K != (target_pos - 1) % K:
            possible = False
            break
    if not possible:
        print(-1)
        return
    
    orbits = [[] for _ in range(K)]
    for original_pos in range(1, N + 1):
        r = (original_pos - 1) % K
        orbits[r].append(original_pos)
    
    total = 0
    for r in range(K):
        pos_list = orbits[r]
        if not pos_list:
            continue
        original_list = [a[i-1] for i in pos_list]
        sorted_values = [sorted_a[i-1] for i in pos_list]
        value_map = {val: i for i, val in enumerate(sorted_values)}
        permutation = [value_map[val] for val in original_list]
        inv_count = count_inversion(permutation)
        total += inv_count
    print(total)

if __name__ == "__main__":
    main()
0