結果

問題 No.1838 Modulo Straight
ユーザー lam6er
提出日時 2025-03-26 15:53:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,657 bytes
コンパイル時間 498 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 170,068 KB
最終ジャッジ日時 2025-03-26 15:54:13
合計ジャッジ時間 8,022 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from bisect import bisect_right

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

    same_inversion = 0
    pos = {}
    for a in A:
        pos.setdefault(a, [])
        pos[a].append(len(pos[a]))
    for a in pos:
        cnt = [0] * (len(pos[a]) + 1)
        def update(i):
            i += 1
            while i < len(cnt):
                cnt[i] += 1
                i += i & -i
        def query(i):
            res = 0
            i += 1
            while i > 0:
                res += cnt[i]
                i -= i & -i
            return res
        for idx in reversed(pos[a]):
            same_inversion += query(idx - 1)
            update(idx)

    min_total = float('inf')

    for x in range(M):
        elements = []
        count = {a: 0 for a in range(M)}
        for a in A:
            k = count[a]
            i_val = (a - x) % M + k * M
            elements.append(i_val)
            count[a] += 1
        sorted_unique = sorted(elements)
        rank = {v: i + 1 for i, v in enumerate(sorted_unique)}
        ft = [0] * (len(elements) + 2)
        res = 0
        for i in reversed(range(len(elements))):
            v = elements[i]
            r = rank[v]
            idx = r
            while idx > 0:
                res += ft[idx]
                idx -= idx & -idx
            idx = r
            while idx < len(ft):
                ft[idx] += 1
                idx += idx & -idx
        total = res + same_inversion
        if total < min_total:
            min_total = total
    print(min_total)

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