2582. When I sort…

单点时限: 2.0 sec

内存限制: 256 MB

In datastruct class, the teacher gives partychen a simple sort question:

A permutation $p[0]$, $p[1]$, …, $p[n-1]$ is a sequence containing each number from $0$ to $n-1$ exactly once. The result of applying permutation $p$ to an array $A$ of length $n$ is an array $B$ of length $n$, where $B[p[i]] = A[i]$ (0-based indices).

Given an array $A$, find a permutation which has the effect of sorting the elements of $A$ in non-descending order, i.e., an order where each element is greater than or equal to the previous one. If there are several suitable permutations output the lexicographically smallest one.

The permutation $p[0]$, $p[1]$, …, $p[n-1]$ is considered lexicographically smaller than the permutation $q[0]$, $q[1]$, …, $q[n-1]$ if there is an index $i$ such that $p[i] < q[i]$ and the equation $p[j] = q[j]$ holds for all $j < i$.


The first line of input gives the number of cases, $N$($1 \leq N \leq 100$). $N$ test cases follow.

In each test case, there are two lines. The first line is a interger $M$($1 \leq M \leq 10000$), representing the numbers of array $A$, and in the second line there are $M$ intergers.


Output the permutation $p$ as discrible above.


2 3 1
2 1 3 1
1 2 0
2 0 3 1


In case 1: The element that is originally at position $0$ goes to position $1$. The elements originally at positions $1$ and $2$ go to positions $2$ and $0$, respectively.
In case 2: There are two suitable permutations: ${2, 0, 3, 1}$ and ${2, 1, 3, 0}$. The first one is lexicographically smaller.

350 人解决,395 人已尝试。

493 份提交通过,共有 868 份提交。

1.4 EMB 奖励。

创建: 14 年,7 月前.

修改: 5 年,2 月前.

最后提交: 4 月,3 周前.

来源: partychen