1365B.md (2157B)
1 Source: https://codeforces.com/problemset/problem/1365/B 2 3 B. Trouble Sort 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Ashish has $n$ elements arranged in a line. 22 23 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$. 24 25 He can perform the following operation any number of times: 26 27 * 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. 28 29 Tell him if he can sort the elements in non-decreasing values of $a_i$ after performing any number of operations. 30 31 Input 32 33 The first line contains one integer $t$ $(1 \le t \le 100)$ — the number of test cases. The description of the test cases follows. 34 35 The first line of each test case contains one integer $n$ $(1 \le n \le 500)$ — the size of the arrays. 36 37 The second line contains $n$ integers $a_i$ $(1 \le a_i \le 10^5)$ — the value of the $i$-th element. 38 39 The third line containts $n$ integers $b_i$ $(b_i \in \{0, 1\})$ — the type of the $i$-th element. 40 41 Output 42 43 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. 44 45 You may print each letter in any case (upper or lower). 46 47 Example 48 49 Input 50 51 ``` 52 5 53 4 54 10 20 20 30 55 0 1 0 1 56 3 57 3 1 2 58 0 1 1 59 4 60 2 2 4 8 61 1 1 1 1 62 3 63 5 15 4 64 0 0 0 65 4 66 20 10 100 50 67 1 0 0 1 68 ``` 69 70 Output 71 72 ``` 73 Yes 74 Yes 75 Yes 76 No 77 Yes 78 ``` 79 80 Note 81 82 For the first case: The elements are already in sorted order. 83 84 For the second case: Ashish may first swap elements at positions $1$ and $2$, then swap elements at positions $2$ and $3$. 85 86 For the third case: The elements are already in sorted order. 87 88 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. 89 90 For the fifth case: Ashish may swap elements at positions $3$ and $4$, then elements at positions $1$ and $2$.