201112: [AtCoder]ARC111 C - Too Heavy
Description
Score : $600$ points
Problem Statement
There are $N$ people numbered $1$ to $N$ and $N$ pieces of baggage numbered numbered $1$ to $N$. Person $i$ has a weight of $a_i$, and Baggage $j$ has a weight of $b_j$. Initially, Person $i$ has Baggage $p_i$. We want to do the operation below zero or more times so that each Person $i$ will have Baggage $i$.
- Choose $i,j (i \neq j)$, and swap the baggages of Person $i$ and Person $j$.
However, when a person has a piece of baggage with a weight greater than or equal to his/her own weight, the person gets tired and becomes unable to take part in a future operation (that is, we cannot choose him/her as Person $i$ or $j$). Particularly, if $a_i \leq b_{p_i}$, Person $i$ cannot take part in any operation.
Determine whether there is a sequence of operations that achieves the objective, and if so, construct one such sequence with the minimum possible number of operations.
Constraints
- $1 \leq N \leq 200000$
- $1 \leq a_i,b_i \leq 10^9$
- $p$ is a permutation of $1, \ldots, N$.
- All numbers in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $a_1$ $a_2$ $\ldots$ $a_N$ $b_1$ $b_2$ $\ldots$ $b_N$ $p_1$ $p_2$ $\ldots$ $p_N$
Output
If no sequence of operations achieves the objective, print -1
.
Otherwise, print a sequence of operations in the following format:
$K$ $i_1$ $j_1$ $i_2$ $j_2$ $:$ $i_K$ $j_K$
Here, $K$ is the number of operations, and $i_t, j_t$ represent the people chosen in the $t$-th operation.
If there are multiple solutions, any of them will be accepted.
Sample Input 1
4 3 4 8 6 5 3 1 3 3 4 2 1
Sample Output 1
3 3 4 1 3 4 2
Initially, People $1, 2, 3, 4$ has pieces of baggage with weights $1, 3, 3, 5$, respectively, so no one is tired.
First, we do the operation choosing Person $3$ and $4$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $1, 3, 5, 3$, so no one is tired yet.
Second, we do the operation choosing Person $1$ and $3$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $5, 3, 1, 3$, so Person $1$ gets tired.
Lastly, we do the operation choosing Person $4$ and $2$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $5, 3, 1, 3$, so no one gets tired.
This sequence of operations has made everyone have the right piece of baggage, with the minimum possible number of operations, so it is valid.
Sample Input 2
4 1 2 3 4 4 3 2 1 4 3 2 1
Sample Output 2
-1
No sequence of operations achieves the objective.
Sample Input 3
1 58 998244353 1
Sample Output 3
0
The objective is already achieved in the initial state.