codeforces-scrape

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

920C.md (1685B)


      1 Source: https://codeforces.com/problemset/problem/920/C
      2 
      3 C. Swap Adjacent Elements
      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 You have an array *a* consisting of *n* integers. Each integer from 1 to *n* appears exactly once in this array.
     22 
     23 For some indices *i* (1 ≤ *i* ≤ *n* - 1) it is possible to swap *i*-th element with (*i* + 1)-th, for other indices it is not possible. You may perform any number of swapping operations any order. There is no limit on the number of times you swap *i*-th element with (*i* + 1)-th (if the position is not forbidden).
     24 
     25 Can you make this array sorted in ascending order performing some sequence of swapping operations?
     26 
     27 Input
     28 
     29 The first line contains one integer *n* (2 ≤ *n* ≤ 200000) — the number of elements in the array.
     30 
     31 The second line contains *n* integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 200000) — the elements of the array. Each integer from 1 to *n* appears exactly once.
     32 
     33 The third line contains a string of *n* - 1 characters, each character is either 0 or 1. If *i*-th character is 1, then you can swap *i*-th element with (*i* + 1)-th any number of times, otherwise it is forbidden to swap *i*-th element with (*i* + 1)-th.
     34 
     35 Output
     36 
     37 If it is possible to sort the array in ascending order using any sequence of swaps you are allowed to make, print YES. Otherwise, print NO.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 6  
     45 1 2 5 3 4 6  
     46 01110
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 YES
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 6  
     59 1 2 5 3 4 6  
     60 01010
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 NO
     67 ```
     68 
     69 Note
     70 
     71 In the first example you may swap *a*3 and *a*4, and then swap *a*4 and *a*5.