結果

問題 No.2665 Minimize Inversions of Deque
ユーザー Yotugi
提出日時 2025-05-27 00:27:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 270 ms / 2,000 ms
コード長 2,114 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 108,528 KB
最終ジャッジ日時 2025-05-27 00:27:37
合計ジャッジ時間 11,804 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin,setrecursionlimit#,set_int_max_str_digits
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
setrecursionlimit(20000000) # これこどふぉだと無理
#set_int_max_str_digits(200010)
mod = 998244353 
ii = lambda :int(stdin.readline())
mi = lambda :map(int,stdin.readline().split())
li = lambda :list(mi())
gmi = lambda :map(lambda x: int(x) - 1, stdin.readline().split())
gi = lambda :list(map(lambda x: 0 if x == "." else 1,input())) # グリッド入力受け取り
py = lambda :print("Yes")
pn = lambda :print("No")
pf = lambda :print("First") 
ps = lambda :print("Second")
vec = [(1,0),(-1,0),(0,-1),(0,1)]
vec1 = [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] #8方向
inf = 2*10**18

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i, j = None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

    #合計値がsを超える最小のインデックス
    def lowerbound(self, s):
        x = 0
        y = 0
        for i in range(self.n.bit_length(), -1, -1):
            k = x + (1 << i)
            if k <= self.n and (y + self.data[k] < s):
                y += self.data[k]
                x += 1 << i
        return x + 1
    
    def show(self):
        print(self.el[1::])


from collections import deque 

def solve():
    n = ii() 
    p = li() 
    fw = BIT(n) 
    ret = 0 
    que = deque() 
    for i in p:
        tmp1 = fw.sum(i)
        tmp2 = fw.get(i,n)
        #print(tmp1,tmp2)
        if tmp1 >= tmp2:
            que.append(i) 
            ret += tmp2 
        else:
            que.appendleft(i) 
            ret += tmp1 
        fw.add(i,1)
        #print(*que)

    print(ret) 
    print(*que)


t = ii() 
for _ in range(t):
    solve()
0