codeforces#P2205A. Simons and Making It Beautiful
-
ID: 42017
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Simons and Making It Beautiful
Problem Description
For a permutation$^{\text{∗}}$ $r$ of length $m$, we call an index $i$ ($1\le i\le m$) ugly if and only if $i=\max(\{r_1,r_2,\ldots,r_i\})$.
Simons has a permutation $p$ of length $n$, and he can perform the following operation on $p$ at most once:
- Choose two indices $i$ and $j$ ($1\le i\ne j\le n$), then swap $p_i$ and $p_j$.
Find a permutation $q$ that can be obtained from $p$ by performing the above operation at most once, such that the number of ugly indices in $q$ is minimized.
$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.
The first line contains an integer $n$ ($1\le n\le 500$) — the length of $p$.
The second line contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$-s are distinct) — the elements of $p$.
For each test case, print $n$ integers $q_1,q_2,\ldots,q_n$ — the permutation you found.
If there are multiple possible permutations, you may output any.
Input Format
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.
The first line contains an integer $n$ ($1\le n\le 500$) — the length of $p$.
The second line contains $n$ integers $p_1,p_2,\ldots,p_n$ ($1\le p_i\le n$, all $p_i$-s are distinct) — the elements of $p$.
Output Format
For each test case, print $n$ integers $q_1,q_2,\ldots,q_n$ — the permutation you found.
If there are multiple possible permutations, you may output any.
5
2
1 2
4
2 3 1 4
5
3 2 4 5 1
1
1
8
4 1 3 2 6 7 8 5
,
2 1
2 4 1 3
3 2 4 5 1
1
4 1 3 8 6 7 2 5
Hint
In the first test case, Simons can obtain only two possible permutations: $[1,2]$ and $[2,1]$.
- For permutation $[1,2]$, we can see $1=\max(\{1\})$ and $2=\max(\{1,2\})$. So there are two ugly indices.
- For permutation $[2,1]$, we can see $1\ne\max(\{2\})$ and $2=\max(\{2,1\})$. So there is only one ugly index.
Thus, permutation $[2,1]$ has the minimum count of ugly indices.
In the second test case, Simons can obtain permutation $[2,4,1,3]$ by choosing indices $2$ and $4$ to swap. There is only one ugly index in the permutation:
- $1\ne \max(\{2\})$, so index $1$ is not ugly;
- $2\ne \max(\{2,4\})$, so index $2$ is not ugly;
- $3\ne \max(\{2,4,1\})$, so index $3$ is not ugly;
- $4=\max(\{2,4,1,3\})$, so index $4$ is ugly.
In the third test case, note that Simons does not perform the operation.