LRSort
SRM 845 · 2023-03-02 · by misof
Problem Statement
Given is a sequence A[0..N-1] of nonnegative integers, each between 0 and M-1, inclusive. We are going to sort this sequence
The sorting will consist of N-1 phases, numbered from 0 to N-2. Each phase is either "type 0" or "type 1".
Also given is a sequence T[0..N-2] of zeros and ones: T[i] is the type of phase i.
In a type 0 phase we locate the leftmost minimum in A and then we move it to the beginning of A by repeatedly swapping it with its left neighbor. Once that is done, we will pretend that this element no longer exists during the following phases.
In a type 1 phase we move the rightmost maximum in A to the end in the same way.
Let S[i] be the number of swaps performed during phase i. Let WS[i] = S[i] * 10^i. Return sum(WS) modulo (10^9 + 7).
Please use the following pseudocode to generate the arrays A and T:
L = length(Aprefix)
for i = 0 to L-1:
A[i] = Aprefix[i]
state = seed
for i = L to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
A[i] = state modulo M
for i = 0 to N-2:
state = (state * 1103515245 + 12345) modulo 2^31
tmp = (state div 2^20) modulo 100
if tmp < B:
T[i] = 1
else:
T[i] = 0
Notes
- The reference solution does not depend on the input being pseudorandom, that is only done to keep the input size small.
Constraints
- N will be between 2 and 500,000, inclusive.
- Aprefix will have between 0 and min(N,200) elements, inclusive.
- Each element of Aprefix will be between 0 and M-1, inclusive.
- M will be between 1 and 10^9, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- B will be between 0 and 100, inclusive.
6
{70, 60, 50, 40, 30, 20}
100
47
74
Returns: 12345
The generated array T should look as follows: T = {1, 1, 0, 1, 0}. Regardless of the phase type, the element we want is always at the opposite end of the currently-unsorted segment of A. Thus, the required numbers of swaps are S = {5, 4, 3, 2, 1}.
10
{4, 7}
10
47474747
47
Returns: 10226283
The generated array A should look as follows: A = {4, 7, 8, 1, 8, 5, 8, 7, 2, 1} The generated array T should look as follows: T = {0, 0, 1, 0, 1, 1, 1, 1, 1} The calculated array S should look as follows: S = {3, 8, 2, 6, 2, 2, 0, 1, 0} For example, in phase 0 we move the leftmost 1 to the beginning of A (3 swaps), then in phase 1 we move the other 1 to the beginning of the rest of A (8 swaps), then in phase 2 we move the rightmost 8 to the end of A (which now only requires 2 swaps), and so on.
47000
{}
1
47
47
Returns: 0
The array A is all zeros. Regardless of the array T, there will never be any swaps.
15
{}
147
777444
42
Returns: 466633400
Remember to calculate the answer modulo 10^9 + 7.
500000
{}
1000007
4777474
47
Returns: 123109382
Submissions are judged against all 35 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LRSort with a public method int simulate(int N, vector<int> Aprefix, int M, int seed, int B) · 35 test cases · 2 s / 256 MB per case