SortingWithPermutation
TCO09 Qual 1 · 2009-02-24 · by FedorTsarev
TCO09 Qual 1 · 2009-02-24 · by FedorTsarev · Sorting
Problem Statement
Problem Statement
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 return 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.
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 return 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.
Constraints
- a will contain between 1 and 50 elements, inclusive.
- Each element of a will be between 1 and 1000, inclusive.
Examples
0)
{2, 3, 1}
Returns: {1, 2, 0 }
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.
1)
{2, 1, 3, 1}
Returns: {2, 0, 3, 1 }
There are two suitable permutations - {2, 0, 3, 1} and {2, 1, 3, 0}. The first one is lexicographically smaller.
2)
{4, 1, 6, 1, 3, 6, 1, 4}
Returns: {4, 0, 6, 1, 3, 7, 2, 5 }
3)
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
4)
{4}
Returns: {0 }
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SortingWithPermutation with a public method vector<int> getPermutation(vector<int> a) · 88 test cases · 2 s / 256 MB per case