結果
問題 | No.366 ロボットソート |
ユーザー | FromBooska |
提出日時 | 2023-04-06 07:31:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 2,691 bytes |
コンパイル時間 | 971 ms |
コンパイル使用メモリ | 81,900 KB |
実行使用メモリ | 63,476 KB |
最終ジャッジ日時 | 2024-10-02 08:33:05 |
合計ジャッジ時間 | 2,892 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
52,736 KB |
testcase_01 | AC | 39 ms
53,924 KB |
testcase_02 | AC | 38 ms
52,616 KB |
testcase_03 | AC | 39 ms
52,916 KB |
testcase_04 | AC | 39 ms
53,480 KB |
testcase_05 | AC | 40 ms
52,396 KB |
testcase_06 | AC | 40 ms
53,584 KB |
testcase_07 | AC | 40 ms
52,880 KB |
testcase_08 | AC | 40 ms
53,292 KB |
testcase_09 | AC | 41 ms
53,444 KB |
testcase_10 | AC | 41 ms
54,484 KB |
testcase_11 | AC | 51 ms
62,604 KB |
testcase_12 | AC | 51 ms
63,476 KB |
testcase_13 | AC | 48 ms
61,140 KB |
testcase_14 | AC | 49 ms
62,020 KB |
testcase_15 | AC | 42 ms
53,764 KB |
testcase_16 | AC | 47 ms
60,888 KB |
testcase_17 | AC | 49 ms
62,048 KB |
testcase_18 | AC | 52 ms
62,432 KB |
testcase_19 | AC | 49 ms
62,080 KB |
testcase_20 | AC | 41 ms
53,488 KB |
testcase_21 | AC | 49 ms
62,820 KB |
testcase_22 | AC | 50 ms
62,356 KB |
ソースコード
# まず数字順で要素を書き直す # modKでグループごとに分ける # それぞれのグループ内にあるべき数字、たとえば135がなければ不可能 # あるべき数字があれば、それぞれのグループ内での転倒数を求め、その和が答えか # バブルソートでの交換回数は転倒数に等しい # https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion N, K = map(int, input().split()) A = list(map(int, input().split())) with_idx = [] for i in range(N): with_idx.append([A[i], i]) with_idx.sort() for i in range(N): with_idx[i].append(i+1) with_idx.sort(key = lambda x:x[1]) groups = [[] for i in range(K)] for i in range(N): groups[i%K].append(with_idx[i][2]) test = True for i in range(K): check_set = set(groups[i]) start = i+1 for j in range(start, N+1, K): if j not in check_set: test = False #print(groups[i], check_set, test) # 転倒数はBinary Indexed Tree BITというデータ構造で高速に求まる # 数列の最大値以上のサイズのBITを用意、最大値がわかっている必要がある # https://scrapbox.io/pocala-kyopro/%E8%BB%A2%E5%80%92%E6%95%B0 # https://nagiss.hateblo.jp/entry/2019/07/01/185421 class Bit: def __init__(self, n): self.size = n self.tree = [0]*(n+1) def __iter__(self): psum = 0 for i in range(self.size): csum = self.sum(i+1) yield csum - psum psum = csum raise StopIteration() def __str__(self): # O(nlogn) return str(list(self)) def sum(self, i): # [0, i) の要素の総和を返す if not (0 <= i <= self.size): raise ValueError("error!") s = 0 while i>0: s += self.tree[i] i -= i & -i return s def add(self, i, x): if not (0 <= i < self.size): raise ValueError("error!") i += 1 while i <= self.size: self.tree[i] += x i += i & -i def __getitem__(self, key): if not (0 <= key < self.size): raise IndexError("error!") return self.sum(key+1) - self.sum(key) def __setitem__(self, key, value): # 足し算と引き算にはaddを使うべき if not (0 <= key < self.size): raise IndexError("error!") self.add(key, value - self[key]) ans = 0 for i in range(K): if len(groups[i]) == 0: continue bit = Bit(max(groups[i])+1) count = 0 for i, a in enumerate(groups[i]): count += i - bit.sum(a+1) bit.add(a, 1) ans += count if test == True: print(ans) else: print(-1)