結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | dp_ijk |
提出日時 | 2024-06-22 16:45:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 319 ms / 2,000 ms |
コード長 | 1,385 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 111,324 KB |
最終ジャッジ日時 | 2024-06-22 16:45:29 |
合計ジャッジ時間 | 11,077 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
class FenwickTree:def __init__(self, iterable):self.tree = tree = [0]tree.extend(iterable)self.data = tree[1:]self.N = N = len(tree) - 1for i in range(1, N+1):if i + (i& -i) <= N:tree[i + (i& -i)] += tree[i]def add(self, i, x):assert 0 <= i < self.Ntree = self.treeself.data[i] += xi += 1while i <= self.N:tree[i] += xi += i& -idef sum(self, l, r):assert 0 <= l <= r <= self.Ntree = self.treeres = 0while l < r:res += tree[r]r &= r-1while l > r:res -= tree[l]l &= l-1return resdef __repr__(self):return repr(self.data)from collections import dequeT = int(input())for _ in range(T):N = int(input())P = list(map(lambda x: int(x) - 1, input().split()))fw = FenwickTree([0]*N)Q = deque()inv = 0for i, p in enumerate(P):xL = fw.sum(0, p)xR = i-xLif xL > xR:Q.append(p)inv += xRif xL < xR:Q.appendleft(p)inv += xLif xL == xR:inv += xLif not Q:Q.append(p)else:if Q[0] > p:Q.appendleft(p)else:Q.append(p)fw.add(p, 1)print(inv)print(*(x+1 for x in Q))