#941215 (Python3) No.2665 Minimize Inversions of Deque

• 問題: No.2665 Minimize Inversions of Deque
• ユーザー: 👑 p-adic
• 提出日時: 2023-12-30 10:10:59
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: AC
• 実行時間: 886 ms / 2,000 ms
• コード長: 399 bytes
• コンパイル時間: 88 ms
• コンパイル使用メモリ: 11,904 KB
• 実行使用メモリ: 32,248 KB
• 最終ジャッジ日時: 2024-01-05 15:03:23
• 合計ジャッジ時間: 22,783 ms
• ジャッジサーバーID （参考情報）: judge15 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	29 ms; 10,112 KB
testcase_01	AC	673 ms; 10,112 KB
testcase_02	AC	645 ms; 10,112 KB
testcase_03	AC	625 ms; 10,112 KB
testcase_04	AC	621 ms; 10,112 KB
testcase_05	AC	628 ms; 10,112 KB
testcase_06	AC	631 ms; 10,112 KB
testcase_07	AC	625 ms; 10,112 KB
testcase_08	AC	626 ms; 10,112 KB
testcase_09	AC	622 ms; 10,112 KB
testcase_10	AC	621 ms; 10,112 KB
testcase_11	AC	625 ms; 10,112 KB
testcase_12	AC	620 ms; 10,112 KB
testcase_13	AC	618 ms; 10,112 KB
testcase_14	AC	618 ms; 10,112 KB
testcase_15	AC	623 ms; 10,112 KB
testcase_16	AC	620 ms; 10,112 KB
testcase_17	AC	632 ms; 10,112 KB
testcase_18	AC	627 ms; 10,112 KB
testcase_19	AC	113 ms; 10,112 KB
testcase_20	AC	45 ms; 10,624 KB
testcase_21	AC	45 ms; 10,496 KB
testcase_22	AC	44 ms; 10,496 KB
testcase_23	AC	46 ms; 10,752 KB
testcase_24	AC	45 ms; 10,752 KB
testcase_25	AC	46 ms; 10,752 KB
testcase_26	AC	45 ms; 10,624 KB
testcase_27	AC	45 ms; 10,624 KB
testcase_28	AC	46 ms; 10,752 KB
testcase_29	AC	46 ms; 10,752 KB
testcase_30	AC	874 ms; 30,616 KB
testcase_31	AC	785 ms; 21,508 KB
testcase_32	AC	818 ms; 23,580 KB
testcase_33	AC	851 ms; 28,060 KB
testcase_34	AC	783 ms; 18,836 KB
testcase_35	AC	865 ms; 31,960 KB
testcase_36	AC	885 ms; 31,960 KB
testcase_37	AC	795 ms; 20,880 KB
testcase_38	AC	859 ms; 26,260 KB
testcase_39	AC	886 ms; 32,248 KB

ソースコード

I,O,R=input,print,range
def A(i,t):
	i+=1
	while i<=N:F[i],i=F[i]+t,i+(i&-i)
def L(r):
	a=0
	i=min(r+1,N)
	while i:a,i=a+F[i],i-(i&-i)
	return a
for t in R(int(I())):
	N,a,X,Y=int(I()),0,[],[]
	P,F=list(map(int,I().split())),[0]*(N+1)
	for i,p in zip(R(N),P):
		c=L(p)
		if c<i-c or not(X or Y)or(i==2*c and X[-1]>p):
			a+=c
			X+=[p]
		else:
			a+=i-c
			Y+=[p]
		A(p,1)
	X.reverse(),O(a),O(*X,*Y)