72 lines
1.6 KiB
Markdown
72 lines
1.6 KiB
Markdown
# 01 Sort
|
||
|
||
## 题目描述
|
||
|
||
给定两个长度为 $n$ 的序列 $a[1...n]$ 和 $b[1...n]$，其中每个 $a[i]$ 都对应一个属性 $b[i]$，并且 $b[i]$ 的取值只能为 $0$ 或者 $1$。
|
||
|
||
定义一次操作的规则如下：
|
||
|
||
- 选择满足 $b[i]\neq b[j]$ 的两个数 $i$ 和 $j \ (1\le i,j\le n, i\neq j)$，分别交换对应的 $a[i],a[j]$ 和 $b[i], b[j]$
|
||
|
||
你最多可以执行 $x\in [0, 10^5]$ 次操作，请你判断能否在规定次数内，使得序列 $a[1...n]$ 排序成非降顺序吗？如果可以，请你输出一种可能的操作方案；如果不可以，则输出 $-1$。
|
||
|
||
## 输入格式
|
||
|
||
第一行包含一个整数 $t$，代表 $t$ 组数据
|
||
|
||
每组数据的第一行保包含 $1$ 个整数 $n$，表示序列长度
|
||
|
||
每组数据的第二行 $n$ 个整数 $a[1...n]$
|
||
|
||
每组数据的第三行 $n$ 个整数 $b[1...n]$，表示每个 $a[i]$ 对应的属性 $0$ 或 $1$
|
||
|
||
## 输出格式
|
||
|
||
请你分别输出 $t$ 组数据的答案。
|
||
|
||
对于每组数据，第一行输出一个整数 $x \ (x\in [0, 10^5])$ 代表操作次数，若无解则输出 $-1$。接下来的 $x$ 行，每行两个整数 $i$ 和 $j$，代表一次操作。
|
||
|
||
如果有多个答案，则打印其中任何一个。你不必尽量减少移动的次数。
|
||
|
||
## 样例 #1
|
||
|
||
### 样例输入 #1
|
||
|
||
```
|
||
5
|
||
4
|
||
10 20 20 30
|
||
0 1 0 1
|
||
3
|
||
3 1 2
|
||
0 1 1
|
||
4
|
||
2 2 4 8
|
||
1 1 1 1
|
||
3
|
||
5 15 4
|
||
0 0 0
|
||
4
|
||
20 10 100 50
|
||
1 0 0 1
|
||
```
|
||
|
||
### 样例输出 #1
|
||
|
||
```
|
||
0
|
||
2
|
||
1 2
|
||
2 3
|
||
0
|
||
-1
|
||
2
|
||
1 2
|
||
3 4
|
||
```
|
||
|
||
## 提示
|
||
|
||
对于 $20\%$ 数据，$1\le t\le 10$，$1\le n\le 100$，$1\le a[i]\le 100$，所有 $b[i]=0$
|
||
|
||
对于 $100\%$ 数据，$1\le t\le 100$，$1\le n\le 10^3$，$1\le a[i]\le 10^5$，$b[i]\in \{0,1\}$ |