結果

問題 No.2665 Minimize Inversions of Deque
ユーザー flygonflygon
提出日時 2024-03-08 21:49:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 386 ms / 2,000 ms
コード長 5,108 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 111,688 KB
最終ジャッジ日時 2024-03-08 21:49:39
合計ジャッジ時間 13,764 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
55,596 KB
testcase_01 AC 383 ms
84,984 KB
testcase_02 AC 362 ms
84,744 KB
testcase_03 AC 311 ms
83,840 KB
testcase_04 AC 323 ms
84,096 KB
testcase_05 AC 355 ms
84,224 KB
testcase_06 AC 322 ms
84,744 KB
testcase_07 AC 313 ms
84,104 KB
testcase_08 AC 364 ms
84,232 KB
testcase_09 AC 346 ms
84,360 KB
testcase_10 AC 320 ms
83,976 KB
testcase_11 AC 318 ms
84,360 KB
testcase_12 AC 311 ms
83,836 KB
testcase_13 AC 314 ms
84,476 KB
testcase_14 AC 319 ms
84,360 KB
testcase_15 AC 348 ms
84,104 KB
testcase_16 AC 328 ms
84,864 KB
testcase_17 AC 317 ms
84,224 KB
testcase_18 AC 348 ms
84,092 KB
testcase_19 AC 210 ms
78,844 KB
testcase_20 AC 121 ms
77,760 KB
testcase_21 AC 121 ms
77,760 KB
testcase_22 AC 115 ms
77,512 KB
testcase_23 AC 103 ms
77,508 KB
testcase_24 AC 114 ms
78,016 KB
testcase_25 AC 104 ms
77,500 KB
testcase_26 AC 122 ms
78,020 KB
testcase_27 AC 115 ms
78,148 KB
testcase_28 AC 106 ms
77,628 KB
testcase_29 AC 103 ms
77,376 KB
testcase_30 AC 386 ms
108,256 KB
testcase_31 AC 378 ms
97,644 KB
testcase_32 AC 360 ms
104,764 KB
testcase_33 AC 374 ms
105,084 KB
testcase_34 AC 355 ms
95,824 KB
testcase_35 AC 299 ms
104,552 KB
testcase_36 AC 296 ms
104,552 KB
testcase_37 AC 337 ms
96,032 KB
testcase_38 AC 366 ms
103,732 KB
testcase_39 AC 369 ms
111,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(5*10**5)
input = sys.stdin.readline
from collections import defaultdict, deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right
from math import gcd
def add(x, y):
    return x + y


def e(a):
    if a == min:
        return 10**18
    if a == max:
        return -10**18
    if a == add:
        return 0


class SegTree:
    def __init__(self, segf, init_val):
        n = len(init_val)
        self.segf = segf
        self.e = e(segf)
        self.seg_len = 1 << n.bit_length()
        self.seg = [self.e] * (self.seg_len<<1)
        for i in range(n):
            self.seg[i + self.seg_len] = init_val[i]
        for i in range(self.seg_len)[::-1]:
            self.seg[i] = segf(self.seg[i << 1], self.seg[i << 1 | 1])

    def point_add(self, pos, x):
        pos += self.seg_len
        self.seg[pos] += x
        while True:
            pos >>= 1
            if not pos:
                break
            self.seg[pos] = self.segf(
                self.seg[pos << 1],  self.seg[pos << 1 | 1])

    def point_update(self, pos, x):
        pos += self.seg_len
        self.seg[pos] = x
        while True:
            pos >>= 1
            if not pos:
                break
            self.seg[pos] = self.segf(
                self.seg[pos << 1],  self.seg[pos << 1 | 1])

    def get_range(self, l, r):
        l += self.seg_len
        r += self.seg_len
        res = self.e
        while l < r:
            if l & 1:
                res = self.segf(res, self.seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.segf(res, self.seg[r])
            l >>= 1
            r >>= 1
        return res
    

    # max_rightをもとめるための条件式
    def j(self, now, i, t):
        return self.segf(now, self.seg[i]) >= t
    
    # 区間内で条件を満たせない場合-1を返す
    # そうでない場合[ql,ans)が条件を満たすような最右のansを返す
    def max_right(self,ql,qr,t):
        l = ql + self.seg_len
        r = qr + self.seg_len
        if not self.j(self.e, l, t): return -1
        left = []
        right = []
        while l < r:
            if l & 1:left.append(l); l += 1
            if r & 1:r -= 1; right.append(r)
            l >>= 1; r >>= 1
        ord = left + right[::-1]
        now = self.e
        pos = -1
        for i in ord:
            if self.j(now, i, t):
                now = self.segf(now, self.seg[i])
            else:
                pos = i
                break
        if pos == -1:return qr
        while True:
            if pos >= self.seg_len:break
            pos <<= 1
            if self.j(now, pos, t):
                now = self.segf(now, self.seg[pos])
                pos += 1
        return pos - self.seg_len
    
    # 区間内で条件を満たせない場合-1を返す
    # そうでない場合(ans,qr)が条件を満たすような最左のansを返す
    def min_left(self,ql,qr,t):
        l = ql + self.seg_len
        r = qr + self.seg_len
        if not self.j(self.e, r-1, t): return -1
        left = []
        right = []
        while l < r:
            if l & 1:left.append(l); l += 1
            if r & 1:r -= 1; right.append(r)
            l >>= 1; r >>= 1
        ord = left + right[::-1]
        now = self.e
        pos = -1
        for i in ord[::-1]:
            if self.j(now, i, t):
                now = self.segf(now, self.seg[i])
            else:
                pos = i
                break
        if pos == -1:return ql-1
        while True:
            if pos >= self.seg_len:break
            pos = (pos<<1) + 1
            if self.j(now, pos, t):
                now = self.segf(now, self.seg[pos])
                pos -= 1
        return pos - self.seg_len

    # ------ dual ------
    def range_add(self, l, r, x):
        l += self.seg_len
        r += self.seg_len
        while l < r:
            if l & 1:
                self.seg[l] = self.segf(x, self.seg[l])
                l += 1
            if r & 1:
                r -= 1
                self.seg[r] = self.segf(x, self.seg[r])
            l >>= 1
            r >>= 1

    def get_point(self, pos):
        pos += self.seg_len
        res = self.seg[pos]
        while True:
            pos >>= 1
            if not pos:
                break
            res = self.segf(res, self.seg[pos])
        return res

def sol():
    n = int(input())    
    p = list(map(int,input().split()))
    p = [i-1 for i in p]
    st = SegTree(add, [1]*n)
    ans = [0]*(n)
    cnt = 0
    r = n-1
    l = 0
    for i in range(n)[::-1]:
        st.point_update(p[i], 0)
        sm = st.get_range(0, p[i])
        bg = st.get_range(p[i], n)
        cnt += min(sm, bg)
        if sm < bg:
            ans[i] = 0
        else:
            ans[i] = 1 

    que = deque([])
    for i in range(n):
        if ans[i] == 0:
            que.appendleft(p[i]+1)
        else:
            que.append(p[i] + 1)
    print(cnt)
    print(*list(que))




    return 


T = int(input())
for i in range(T):
    sol()
0