結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | PNJ |
提出日時 | 2024-03-08 22:17:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 296 ms / 2,000 ms |
コード長 | 1,160 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,424 KB |
実行使用メモリ | 108,116 KB |
最終ジャッジ日時 | 2024-09-29 19:48:35 |
合計ジャッジ時間 | 9,878 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
from collections import deque class BIT: # 長さN+1の配列を初期化 def __init__(self, N): self.size = N self.bit = [0]*(N+1) # i番目までの和を求める def sum(self, i): if i == 0: return 0 res = 0 while i > 0: res += self.bit[i] # フェニック木のi番目の値を加算 i -= -i & i # 最も右にある1の桁を0にする return res # i番目の値にxを足して更新する def add(self, i, x): while i <= self.size: self.bit[i] += x # フェニック木のi番目にxを足して更新 i += -i & i # 最も右にある1の桁に1を足す T = int(input()) for _ in range(T): n = int(input()) P = list(map(int,input().split())) bit = BIT(n) x = 0 A = deque([P[0]]) bit.add(P[0],1) for i in range(1,n): p = P[i] a = bit.sum(p) b = bit.sum(n) - bit.sum(p) if a < b: A.appendleft(p) elif a > b: A.append(p) else: if A[0] < p: A.append(p) else: A.appendleft(P) x += min(a,b) bit.add(p,1) print(x) print(*A)