UnsortedSequence
SRM 531 · 2011-11-22 · by Mimino
Problem Statement
We say that the sequence of numbers {s[0], s[1], s[2], ..., s[N-1]} is sorted in ascending order if we have s[i] <= s[i+1] for each i between 0 and N-2, inclusive.
For example, the sequences {1,2,3}, {1,1,1}, and {2,2,4,4,6,6} are sorted in ascending order, but the sequences {1,2,1}, {7,4,6}, and {3,2,1} are not.
You are given the sequence of numbers as a
Notes
- Sequence of numbers A is lexicographically smaller than B if A contains a smaller number on the first position on which they differ.
- The sequence s may contain duplicates.
- Note that the sequence consisting of only one element is always sorted.
Constraints
- s will contain between 1 and 50 elements, inclusive.
- Each element of s will be between 1 and 1000, inclusive.
{1,2}
Returns: {2, 1 }
There is only one possible sequence that is not in ascending order: {2,1}.
{1,2,3}
Returns: {1, 3, 2 }
Out of all six possible sequences, five are not in ascending order. Here they are, in lexicographic order: {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}
{7,2,2}
Returns: {2, 7, 2 }
Remember, that the given sequence may contain duplicates.
{1000}
Returns: { }
As mentioned in the Notes section, the sequence consisting of only one element is always sorted. So there is no possibility to unsort this sequence.
{1,1}
Returns: { }
There are also some longer sequences that cannot be unsorted.
Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class UnsortedSequence with a public method vector<int> getUnsorted(vector<int> s) · 89 test cases · 2 s / 256 MB per case