cho.shresearchmini
ProblemCode
Description
Time limit
Memory limit
cho.shTime limit
Memory limit
Let A be a permutation that contains every integer from 0 to N-1 exactly once. From A, define an array B of the same length as follows.
If the resulting B is also a permutation, then A is called a perfect permutation.
The table below shows every permutation A of length 3 and its child array B. The permutations {1, 2, 0} and {2, 0, 1} are perfect because their child arrays are also permutations.
| A | B |
|---|---|
| 0, 1, 2 | 0, 0, 0 |
| 0, 2, 1 | 0, 0, 0 |
| 1, 0, 2 | 0, 1, 0 |
| 1, 2, 0 | 0, 1, 2 |
| 2, 0, 1 | 0, 2, 1 |
| 2, 1, 0 | 0, 2, 0 |
Given a permutation P of length N, output a perfect permutation Q whose difference from P is as small as possible. The difference between P and Q is the number of indices i for which P[i] and Q[i] are different.
The first line contains the size N of the permutation (1 ≤ N ≤ 50). The second line contains N integers, the permutation P[0], P[1], ..., P[N-1], separated by spaces.
Print a perfect permutation Q whose difference from P is minimum. If there are multiple possible Q, print the one whose child array B is lexicographically smallest.