Aizhan has a sequence of
Ermek and Aizhan are going to modify the sequence in a series of rounds. In each round, first Ermek makes a swap and then Aizhan makes another swap. More precisely, the person making a swap chooses two valid indices and swaps the elements at those indices. Note that the two indices do not have to be distinct. If they are equal, the current person swaps an element with itself, which does not change the sequence.
Aizhan knows that Ermek does not actually care about sorting the sequence
Aizhan wants to sort the sequence
Note that if Aizhan sees that the sequence
Example 1
Suppose that:
- The initial sequence is
. - Ermek is willing to make
swaps. - The sequences
and that describe the indices Ermek is going to choose are and . In other words, the pairs of indices that Ermek plans to choose are , , , , , and .
In this setting Aizhan can sort the sequence
The following table shows how Ermek and Aizhan modify the sequence.
Round | Player | Pair of swapped indices | Sequence |
---|---|---|---|
beginning | |||
Ermek | |||
Aizhan | |||
Ermek | |||
Aizhan | |||
Ermek | |||
Aizhan |
Example 2
Suppose that:
- The initial sequence is
. - Ermek is willing to make
swaps. - The pairs of indices that Ermek plans to choose are
, , , , and .
In this setting Aizhan can sort the sequence
Round | Player | Pair of swapped indices | Sequence |
---|---|---|---|
beginning | |||
Ermek | |||
Aizhan | |||
Ermek | |||
Aizhan | |||
Ermek | |||
Aizhan |
Task
You are given the sequence
You need to implement:
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
- This function will be called by the grader exactly once.
N
: the length of the sequence .S
: an array of integers containing the initial sequence .M
: the number of swaps Ermek plans to make.X
,Y
: arrays of integers of length . For , in round Ermek plans to swap numbers at indices and .P
,Q
: arrays of integers. Use these arrays to report one possible sequence of swaps Aizhan can make to sort the sequence . Denote by the length of the sequence of swaps that your program has found. For each between and inclusive, the indices Aizhan should choose in round should be stored into and . You may assume that the arraysP
andQ
have already been allocated to elements each.- This function should return the value of
(defined above).
Subtasks
subtask | points | extra constraints on |
requirement on | ||
---|---|---|---|---|---|
1 | 8 | ||||
2 | 12 | ||||
3 | 16 | ||||
4 | 18 | none | |||
5 | 20 | none | minimum possible | ||
6 | 26 | none | minimum possible |
You may assume that there exists a solution that requires
Comments