codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.