problem.txt (2837B)
1 B. Trouble Sort 2 time limit per test1 second 3 memory limit per test256 megabytes 4 Ashish has n 5 elements arranged in a line. 6 7 These elements are represented by two integers ai 8 — the value of the element and bi 9 — the type of the element (there are only two possible types: 0 10 and 1 11 ). He wants to sort the elements in non-decreasing values of ai 12 . 13 14 He can perform the following operation any number of times: 15 16 Select any two elements i 17 and j 18 such that bi≠bj 19 and swap them. That is, he can only swap two elements of different types in one move. 20 Tell him if he can sort the elements in non-decreasing values of ai 21 after performing any number of operations. 22 23 Input 24 The first line contains one integer t 25 (1≤t≤100) 26 — the number of test cases. The description of the test cases follows. 27 28 The first line of each test case contains one integer n 29 (1≤n≤500) 30 — the size of the arrays. 31 32 The second line contains n 33 integers ai 34 (1≤ai≤105) 35 — the value of the i 36 -th element. 37 38 The third line containts n 39 integers bi 40 (bi∈{0,1}) 41 — the type of the i 42 -th element. 43 44 Output 45 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. 46 47 You may print each letter in any case (upper or lower). 48 49 --- 50 51 Thoughts: 52 53 - n elements in a line 54 - each element is [a_i,b_i] where b \in {0,1} and a_i is an int 55 - sort ascending a_i 56 - can only swap elements of different kinds (b_i != b_j) at each step 57 - return yes / no if he can/can't sort 58 59 --- 60 61 approach: 62 - sort a, see if a can be arranged like that with swaps 63 - min swap problem basically 64 - elements of same value exist though 65 - what are impossible cases 66 - since we can do 0->1->0 are there any? 67 - are we doing exhaustive search? 68 - seems unlikely even though only 500 elements at most 69 - could we do something like bubble sort? 70 - at each step we swap the current with a smaller if possible 71 - stop once can't do this anymore 72 - doesn't work for 73 - 4 3 2 1 74 - 0 0 0 1 75 - is this just always true if > 1 of each? 76 - 77 78 79 --- 80 81 82 Examples: 83 84 10 20 20 30 85 0 1 0 1 86 87 yes, already 88 89 90 3 1 2 91 0 1 1 92 93 1 3 2 94 1 0 1 95 96 1 2 3 97 1 1 0 98 99 so in this one we just find the index that wants our position and we swap with it 100 101 2 2 4 8 102 1 1 1 1 103 104 done 105 106 5 15 4 107 0 0 0 108 109 done 110 111 20 10 100 50 112 1 0 0 1 113 114 target: 10 20 50 100 115 116 10 20 100 50 117 0 1 0 1 118 119 10 20 50 100 120 121 122 --- 123 124 so in this one we just find the index that wants our position and we swap with it 125 126 this doesn't work because: 127 128 10 20 40 15 129 0 1 0 1 130 131 instead we must: 132 133 - iterate over all elements, ask that question again 134 135 --- 136 137 duh, if there are elements of diff types we can use them to proxy swapping. 138 139 140 if count(0) >= 1 and count(1) >= 1: 141 - yes 142 143 one doesn't have any: 144 - no swaps, is it good right now?