問題一覧 > 通常問題

No.2665 Minimize Inversions of Deque

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 115
作問者 : suisen / テスター : 👑 p-adic cureskol ygussany
お気に入りにしたユーザー ProblemId : 10493 / 自分の提出
問題文最終更新日: 2024-02-29 19:02:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 420 (順位表) の他の問題:

Problem Statement

You are given a permutation $P=(P_1,P_2,\ldots,P_n)$ of $(1,2,\ldots,n)$.

The sequence $A$ is initially empty, and you perform the following operation in the order $i=1,2,\ldots,n$.

  • Add $P_i$ to the front or the back of $A$.

Find the minimum possible inversion number of $A$ after all operations have been performed.

Also, find the lexicographically smallest $A$ among those that achieve the minimum inversion number.

In $1$ file, $T$ test cases are given; solve the above problem for all of them.

Definition of inversion number

The inversion number of a sequence $X=(X_1,X_2,\ldots,X_m)$ is the number of integer pairs $(i,j)$ satisfying $1\leq i\lt j\leq m$ and $X_i\gt X_j$.

Definition of lexicographic order

For sequences $X=(X_1,X_2,\ldots,X_m),\ Y=(Y_1,Y_2,\ldots,Y_m)$, if $X\neq Y$, there exists a unique $i\in\lbrace 1,2,\ldots,m\rbrace$ satisfying the following $2$ conditions.
  1. $X_j=Y_j$ for every positive integer $j$ less than $i$
  2. $X_i\neq Y_i$

For such $i$, $X$ is said to be lexicographically smaller than $Y$ if and only if $X_i\lt Y_i$.

Input

The input is given from Standard Input in the following format.

$T$
$\mathrm{testcase}_1$
$\mathrm{testcase}_2$
$\vdots$
$\mathrm{testcase}_T$

Here, for $i=1,2,\ldots,T$, $\mathrm{testcase}_i$ represents the $i$-th test case and is given in the following format.

$n$
$P_1$ $P_2$ $\cdots$ $P_n$
  • All input values are integers.
  • $1\leq T\leq 2\times 10 ^ 5$
  • $1\leq n\leq 2\times 10 ^ 5$
  • $1\leq P_i \leq n$
  • $P$ is a permutation of $(1,2,\ldots,n)$.
  • The sum of $n$ over the $T$ test cases is at most $2\times 10 ^ 5$.

Output

Output the answer for each test case in the following format.

Output the minimum inversion number $x$ of $A$ after all operations have been performed, and the lexicographically smallest $A$ among those that achieve the minimum inversion number, in the following format, followed by a newline.

$x$
$A_1$ $A_2$ $\cdots$ $A_n$

Sample

Sample 1
Input
2
4
1 4 3 2
5
5 4 3 2 1
Output
2
2 1 4 3
0
1 2 3 4 5
  • About the 1st test case

    This input represents $n=4,\ P=(1,4,3,2)$.

    For example, operating as follows makes the final $A$ equal to $(2,1,4,3)$.

    1. Add $P_1=1$ to the front of $A=()$ (the empty sequence), resulting in $A=(1)$.
    2. Add $P_2=4$ to the back of $A=(1)$, resulting in $A=(1,4)$.
    3. Add $P_3=3$ to the back of $A=(1,4)$, resulting in $A=(1,4,3)$.
    4. Add $P_4=2$ to the front of $A=(1,4,3)$, resulting in $A=(2,1,4,3)$.

    The inversion number of this $A$ is $2$. It can be proved that the inversion number cannot be made less than $2$, and that no sequence with inversion number $2$ that is lexicographically smaller than $A$ can be obtained, so the answer for this input is $(2,1,4,3)$.

    In particular, $A=(2,3,1,4)$ is a possible final $A$ and its inversion number is $2$, but it is lexicographically larger than $(2,1,4,3)$, so it is not a correct answer.

  • About the 2nd test case

    This input represents $n=5,\ P=(5,4,3,2,1)$. Choosing to add to the front for all of $i=1,2,3,4,5$ results in $A=(1,2,3,4,5)$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。