/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N の番号がついた N 人の人間と、同じく 1 から N の番号がついた N 個の荷物があります。 人 i の体重は a_i, 荷物 j の重さは b_j です。 はじめ人 i は 荷物 p_i を持っており、以下の操作を 0 回以上繰り返すことで全ての人が自分と同じ番号の荷物を持っている状態にしたいです。
- i,j (i \neq j) を選び、人 i と人 j の荷物を交換する。
ただし、人は自分の体重以上の重さの荷物を持つと疲れてしまい、その後一切操作には加われません (すなわち、i,jとして選べません)。 特に、 a_i \leq b_{p_i} なら一度も操作に加われません。
条件を満たす操作列があるか判定し、存在するならばそのうち操作回数が最小であるものをひとつ構成してください。
制約
- 1 \leq N \leq 200000
- 1 \leq a_i,b_i \leq 10^9
- p は 1, \ldots ,N の順列
- 入力される数はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \ldots a_N b_1 b_2 \ldots b_N p_1 p_2 \ldots p_N
出力
どのように操作しても条件を満たせない場合、-1 を出力せよ。
条件を満たすことが可能な場合、以下のフォーマットで操作列を出力せよ。
K i_1 j_1 i_2 j_2 : i_K j_K
ここで K は操作回数であり、 i_t,j_t は t 回目の操作で選んだ人間の番号である。
解が複数存在する場合、どれを出力しても構わない。
入力例 1
4 3 4 8 6 5 3 1 3 3 4 2 1
出力例 1
3 3 4 1 3 4 2
初期状態で人 1,2,3,4 が持っている荷物の重さはそれぞれ 1,3,3,5 なので、初期状態では誰も疲れていません。
まず人 3 と 4 で操作をします。人 1,2,3,4 が持っている荷物の重さはそれぞれ 1,3,5,3 なので、まだ誰も疲れていません。
次に人 1 と 3 で操作をします。人 1,2,3,4 が持っている荷物の重さはそれぞれ 5,3,1,3 なので、人 1 が疲れます。
最後に人 4 と 2 で操作をします。人 1,2,3,4 が持っている荷物の重さはそれぞれ 5,3,1,3 なので、これで新たに疲れる人はいません。
これによって全員が正しい荷物を持っている状態になり、さらにこれは最小の操作回数なので、正しい出力の一つです。
入力例 2
4 1 2 3 4 4 3 2 1 4 3 2 1
出力例 2
-1
条件を満たすように操作することは出来ません。
入力例 3
1 58 998244353 1
出力例 3
0
初期状態で条件を満たしています。
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.