Trouble Sort
Contest: Codeforces Round 648 (Div. 2)
Difficulty rating: 1300
Tags: constructive algorithms, implementation

Ashish has $$$n$$$ elements arranged in a line.

These elements are represented by two integers $$$a_i$$$ — the value of the element and $$$b_i$$$ — the type of the element (there are only two possible types: $$$0$$$ and $$$1$$$). He wants to sort the elements in non-decreasing values of $$$a_i$$$.

He can perform the following operation any number of times:

- Select any two elements $$$i$$$ and $$$j$$$ such that $$$b_i \ne b_j$$$ and swap them. That is, he can only swap two elements of different types in one move.

Tell him if he can sort the elements in non-decreasing values of $$$a_i$$$ after performing any number of operations.

Input format:
The first line contains one integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the size of the arrays.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \le a_i \le 10^5)$$$  — the value of the $$$i$$$-th element.

The third line containts $$$n$$$ integers $$$b_i$$$ $$$(b_i \in \{0, 1\})$$$  — the type of the $$$i$$$-th element.

Output format:
For each test case, print "Yes" or "No" (without quotes) depending on whether it is possible to sort elements in non-decreasing order of their value.

You may print each letter in any case (upper or lower).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first case: The elements are already in sorted order.

For the second case: Ashish may first swap elements at positions $$$1$$$ and $$$2$$$, then swap elements at positions $$$2$$$ and $$$3$$$.

For the third case: The elements are already in sorted order.

For the fourth case: No swap operations may be performed as there is no pair of elements $$$i$$$ and $$$j$$$ such that $$$b_i \ne b_j$$$. The elements cannot be sorted.

For the fifth case: Ashish may swap elements at positions $$$3$$$ and $$$4$$$, then elements at positions $$$1$$$ and $$$2$$$.

Example input:
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

Example output:
Yes
Yes
Yes
No
Yes

Editorial:
Key Idea:
If there is at least one element of type $$$0$$$ and at least one element of type $$$1$$$, we can always sort the array.
Solution:
If all the elements are of the same type, we cannot swap any two elements. So, in this case, we just need to check if given elements are already in sorted order.
Otherwise, there is at least one element of type $$$0$$$ and at least one element of type $$$1$$$. In this case, it is possible to swap any two elements! We can swap elements of different types using only one operation. Suppose we want to swap two elements $$$a$$$ and $$$b$$$ of the same type. We can do it in $$$3$$$ operations. Let $$$c$$$ be an element of the type different from $$$a$$$ and $$$b$$$. We can first swap $$$a$$$ and $$$c$$$, then swap $$$b$$$ and $$$c$$$ and then swap $$$a$$$ and $$$c$$$ again. In doing so, $$$c$$$ remains at its initial position and $$$a$$$, $$$b$$$ are swapped. This is exactly how we swap two integers using a temporary variable. Since we can swap any two elements, it is always possible to sort the array in this case.
Time complexity: $$$O(n)$$$