Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
長さ N の整数列 A=(A_1, A_2, \dots, A_N), B=(B_1, B_2, \dots, B_N) が与えられます。
あなたは以下の操作を好きな回数行うことができます。
- A_i+A_{i+1}+A_{i+2} が偶数であるような整数 i\ (1 \leq i \leq N-2) を選ぶ。そして A_i, A_{i+1}, A_{i+2} を好きに並び替える。
A を B に一致させることができるか判定してください。
制約
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 2 \times 10^5
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
A を B に一致させることが可能な場合は Yes
を、そうでない場合は No
を出力せよ。
入力例 1
5 1 2 3 4 5 3 1 2 4 5
出力例 1
Yes
A_1+A_2+A_3 は 1+2+3=6 であり偶数なので、操作では i=1 を選ぶことができます。
i=1 を選んで操作し、A_1, A_2, A_3 を A_3, A_1, A_2 に並び替えると、 A は (3, 1, 2, 4, 5) に変化します。
この操作により A を B に一致させることができるので、 Yes
を出力します。
入力例 2
5 1 2 4 6 5 5 1 4 2 6
出力例 2
No
入力例 3
9 2 10 4 3 6 2 6 8 5 2 4 10 3 8 6 6 2 5
出力例 3
Yes
Score : 700 points
Problem Statement
You are given integer sequences of length N: A=(A_1, A_2, \dots, A_N) and B=(B_1, B_2, \dots, B_N).
You may perform the following operation any number of times:
- Choose an integer i\ (1 \leq i \leq N-2) such that A_i+A_{i+1}+A_{i+2} is even. Then, rearrange A_i, A_{i+1}, A_{i+2} as you like.
Determine whether it is possible to make A equal B.
Constraints
- 3 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq 2 \times 10^5
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
If it is possible to make A equal B, print Yes
; otherwise, print No
.
Sample Input 1
5 1 2 3 4 5 3 1 2 4 5
Sample Output 1
Yes
A_1+A_2+A_3 is 1+2+3=6, which is even, so you can choose i=1.
If you choose i=1 and rearrange A_1, A_2, A_3 into A_3, A_1, A_2, then A becomes (3, 1, 2, 4, 5).
Now A equals B, so you should print Yes
.
Sample Input 2
5 1 2 4 6 5 5 1 4 2 6
Sample Output 2
No
Sample Input 3
9 2 10 4 3 6 2 6 8 5 2 4 10 3 8 6 6 2 5
Sample Output 3
Yes