結果
問題 | No.2665 Minimize Inversions of Deque |
ユーザー | flygon |
提出日時 | 2024-03-08 21:49:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 385 ms / 2,000 ms |
コード長 | 5,108 bytes |
コンパイル時間 | 498 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 112,276 KB |
最終ジャッジ日時 | 2024-09-29 19:29:48 |
合計ジャッジ時間 | 13,448 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
import syssys.setrecursionlimit(5*10**5)input = sys.stdin.readlinefrom collections import defaultdict, deque, Counterfrom heapq import heappop, heappushfrom bisect import bisect_left, bisect_rightfrom math import gcddef add(x, y):return x + ydef e(a):if a == min:return 10**18if a == max:return -10**18if a == add:return 0class SegTree:def __init__(self, segf, init_val):n = len(init_val)self.segf = segfself.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_lenself.seg[pos] += xwhile True:pos >>= 1if not pos:breakself.seg[pos] = self.segf(self.seg[pos << 1], self.seg[pos << 1 | 1])def point_update(self, pos, x):pos += self.seg_lenself.seg[pos] = xwhile True:pos >>= 1if not pos:breakself.seg[pos] = self.segf(self.seg[pos << 1], self.seg[pos << 1 | 1])def get_range(self, l, r):l += self.seg_lenr += self.seg_lenres = self.ewhile l < r:if l & 1:res = self.segf(res, self.seg[l])l += 1if r & 1:r -= 1res = self.segf(res, self.seg[r])l >>= 1r >>= 1return 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_lenr = qr + self.seg_lenif not self.j(self.e, l, t): return -1left = []right = []while l < r:if l & 1:left.append(l); l += 1if r & 1:r -= 1; right.append(r)l >>= 1; r >>= 1ord = left + right[::-1]now = self.epos = -1for i in ord:if self.j(now, i, t):now = self.segf(now, self.seg[i])else:pos = ibreakif pos == -1:return qrwhile True:if pos >= self.seg_len:breakpos <<= 1if self.j(now, pos, t):now = self.segf(now, self.seg[pos])pos += 1return pos - self.seg_len# 区間内で条件を満たせない場合-1を返す# そうでない場合(ans,qr)が条件を満たすような最左のansを返すdef min_left(self,ql,qr,t):l = ql + self.seg_lenr = qr + self.seg_lenif not self.j(self.e, r-1, t): return -1left = []right = []while l < r:if l & 1:left.append(l); l += 1if r & 1:r -= 1; right.append(r)l >>= 1; r >>= 1ord = left + right[::-1]now = self.epos = -1for i in ord[::-1]:if self.j(now, i, t):now = self.segf(now, self.seg[i])else:pos = ibreakif pos == -1:return ql-1while True:if pos >= self.seg_len:breakpos = (pos<<1) + 1if self.j(now, pos, t):now = self.segf(now, self.seg[pos])pos -= 1return pos - self.seg_len# ------ dual ------def range_add(self, l, r, x):l += self.seg_lenr += self.seg_lenwhile l < r:if l & 1:self.seg[l] = self.segf(x, self.seg[l])l += 1if r & 1:r -= 1self.seg[r] = self.segf(x, self.seg[r])l >>= 1r >>= 1def get_point(self, pos):pos += self.seg_lenres = self.seg[pos]while True:pos >>= 1if not pos:breakres = self.segf(res, self.seg[pos])return resdef 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 = 0r = n-1l = 0for 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] = 0else:ans[i] = 1que = 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))returnT = int(input())for i in range(T):sol()