← 返回题目列表

Codeforces · 1365/B

B. 故障排序

中文机器翻译题面 查看原题

Ashish 有 $$$n$$$ 元素排列成一行。

这些元素由两个整数 $$$a_i$$$ 表示 - 元素的值和 $$$b_i$$$ - 元素的类型(只有两种可能的类型:$$$0$$$ 和 $$$1$$$)。他想要对 $$$a_i$$$ 的非递减值中的元素进行排序。

他可以执行以下操作任意次:

- 选择任意两个元素 $$$i$$$ 和 $$$j$$$ 使得 $$$b_i \ne b_j$$$ 并交换它们。也就是说,他一招只能交换两种不同类型的元素。

告诉他在执行任意次数的操作后是否可以对 $$$a_i$$$ 中非递减值的元素进行排序。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 100)$$$ — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 500)$$$ — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ $$$(1 \le a_i \le 10^5)$$$ — 第 $$$i$$$ 个元素的值。

第三行包含 $$$n$$$ 整数 $$$b_i$$$ $$$(b_i \in \{0, 1\})$$$ — 第 $$$i$$$ 个元素的类型。

输出

对于每个测试用例,根据是否可以按元素值的非递减顺序对元素进行排序,打印“是”或“否”(不带引号)。

您可以以任何大小写方式打印每个字母(大写或小写)。

示例

输入 #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

Yes
Yes
Yes
No
Yes

注意

对于第一种情况:元素已经按排序顺序排列。

对于第二种情况:Ashish可以首先交换位置$$$1$$$和$$$2$$$处的元素,然后交换位置$$$2$$$和$$$3$$$处的元素。

对于第三种情况:元素已经按排序顺序排列。

对于第四种情况:不能执行交换操作,因为不存在满足 $$$b_i \ne b_j$$$ 的元素对 $$$i$$$ 和 $$$j$$$。元素无法排序。

对于第五种情况:Ashish 可以交换位置 $$$3$$$ 和 $$$4$$$ 处的元素,然后交换位置 $$$1$$$ 和 $$$2$$$ 处的元素。