結果

問題 No.1838 Modulo Straight
ユーザー lam6er
提出日時 2025-04-09 20:57:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,988 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 82,700 KB
実行使用メモリ 236,144 KB
最終ジャッジ日時 2025-04-09 20:58:47
合計ジャッジ時間 7,510 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    M, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    MK = M * K

    # Precompute S_v: for each value v, list of indices in order they appear
    S = defaultdict(list)
    for idx, num in enumerate(A):
        S[num].append(idx)
    for v in S:
        S[v].sort()  # Although they are appended in order, so already sorted

    min_inv = float('inf')

    for x in range(M):
        # Generate for each value v the target positions for current x
        target_pos = defaultdict(list)
        for j in range(MK):
            v_j = (x + j) % M
            target_pos[v_j].append(j)
        
        # Check if all target_pos[v] has exactly K elements (should always be true)
        # Now, for each value v, sorted target positions are already in order
        
        # For each element in original array, assign to the target positions in order
        perm = [0] * MK
        for v in target_pos:
            tars = target_pos[v]
            srcs = S[v]
            for i in range(len(tars)):
                perm[srcs[i]] = tars[i]
        
        # Compute inversion count of perm
        inv = 0
        # Coordinate compression for Fenwick Tree
        sorted_perm = sorted(set(perm))
        rank = {v: i + 1 for i, v in enumerate(sorted_perm)}
        size = len(sorted_perm)
        fenwick = [0] * (size + 2)
        
        for i in reversed(range(MK)):
            p = rank[perm[i]]
            # Query sum of elements < p
            idx = p - 1
            res = 0
            while idx > 0:
                res += fenwick[idx]
                idx -= idx & -idx
            inv += res
            # Update Fenwick Tree
            idx = p
            while idx <= size:
                fenwick[idx] += 1
                idx += idx & -idx
        
        if inv < min_inv:
            min_inv = inv

    print(min_inv)

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