結果
問題 |
No.2382 Amidakuji M
|
ユーザー |
![]() |
提出日時 | 2025-03-20 21:05:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 136 ms / 2,000 ms |
コード長 | 1,154 bytes |
コンパイル時間 | 280 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 108,384 KB |
最終ジャッジ日時 | 2025-03-20 21:05:25 |
合計ジャッジ時間 | 2,981 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
class FenwickTree: def __init__(self, size): self.n = size self.tree = [0] * (self.n + 1) def update(self, idx, delta): while idx <= self.n: self.tree[idx] += delta idx += idx & -idx def query(self, idx): res = 0 while idx > 0: res += self.tree[idx] idx -= idx & -idx return res def compute_inversion(p): max_val = len(p) ft = FenwickTree(max_val) inv_count = 0 for x in reversed(p): inv_count += ft.query(x - 1) ft.update(x, 1) return inv_count n, m = map(int, input().split()) p = list(map(int, input().split())) # Check if already sorted is_sorted = all(p[i] == i + 1 for i in range(n)) if is_sorted: print(0) else: s = compute_inversion(p) if m % 2 == 0: if s % 2 != 0: print(-1) else: t_min = (s + m - 1) // m print(t_min * m) else: t_min = (s + m - 1) // m required_parity = s % 2 if (t_min % 2) == required_parity: print(t_min * m) else: print((t_min + 1) * m)