結果

問題 No.1838 Modulo Straight
ユーザー gew1fw
提出日時 2025-06-12 19:08:19
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,551 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 99,840 KB
最終ジャッジ日時 2025-06-12 19:08:35
合計ジャッジ時間 10,325 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 2 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_left

def main():
    sys.setrecursionlimit(1 << 25)
    M, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    N = M * K

    # Precompute C1
    # For each x, collect the original indices sorted
    occurrences = [[] for _ in range(M)]
    for idx, x in enumerate(A):
        occurrences[x].append(idx)
    # For each x, sort their occurrences
    for x in range(M):
        occurrences[x].sort()
    # For each element, determine its j (0-based in occurrences[x])
    j_list = [0] * N
    for x in range(M):
        for j, idx in enumerate(occurrences[x]):
            j_list[idx] = j

    # Compute C1 using Fenwick Tree
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (size + 2)
        def update(self, idx, delta=1):
            idx += 1  # 1-based
            while idx <= self.size + 1:
                self.tree[idx] += delta
                idx += idx & -idx
        def query(self, idx):
            # sum [0..idx]
            idx += 1  # 1-based
            res = 0
            while idx > 0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res

    C1 = 0
    max_j = K - 1
    ft = FenwickTree(max_j)
    for idx in reversed(range(N)):
        j = j_list[idx]
        C1 += ft.query(j - 1)
        ft.update(j)
    # Precompute for each j group
    j_groups = [[] for _ in range(K)]
    for x in range(M):
        for j in range(K):
            idx = occurrences[x][j]
            j_groups[j].append((idx, x))
    # Sort each j group by original index
    for j in range(K):
        j_groups[j].sort()
        j_groups[j] = [x for idx, x in j_groups[j]]

    # Function to compute C2(s)
    def compute_C2(s):
        res = 0
        for j in range(K):
            group = j_groups[j]
            # Compute the list of (x - s) mod M
            modified = [(x - s) % M for x in group]
            # Count inversions in modified using Fenwick Tree
            ft_inner = FenwickTree(M)
            inv_count = 0
            for val in reversed(modified):
                inv_count += ft_inner.query(val - 1)
                ft_inner.update(val)
            res += inv_count
        return res

    # Find the s that minimizes C1 + C2(s)
    min_inv = float('inf')
    for s in range(M):
        current = C1 + compute_C2(s)
        if current < min_inv:
            min_inv = current
    print(min_inv)

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