Algorithm

C. Swap Adjacent Elements
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/920/C
input
standard input
output
standard output

You have an array a consisting of n integers. Each integer from 1 to n appears exactly once in this array.

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

Can you make this array sorted in ascending order performing some sequence of swapping operations?

Input

The first line contains one integer n (2 ≤ n ≤ 200000) — the number of elements in the array.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 200000) — the elements of the array. Each integer from 1 to n appears exactly once.

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.

Output

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.

Examples
input
Copy
6
1 2 5 3 4 6
01110
output
Copy
YES
input
Copy
6
1 2 5 3 4 6
01010
output
Copy
NO
Note

In the first example you may swap a3 and a4, and then swap a4 and a5.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int a[int(2e5 + 2)], cs[int(2e5 + 2)];

int main() {
	int n;
	cin >> n;

	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

	string s;
	cin >> s;

	cs[0] = 0;
	for(int i = 1; i <= s.length(); ++i)
		cs[i] = cs[i - 1] + (s[i - 1] - '0');

	for(int i = 1; i <= n; ++i) {
		if(a[i] != i) {
			if(a[i] < i) {
				if(i - a[i] != cs[i - 1] - cs[a[i] - 1]) {
					cout << "NO" << endl;
					return 0;
				}
			} else {
				if(a[i] - i != cs[a[i] - 1] - cs[i - 1]) {
					cout << "NO" << endl;
					return 0;
				}
			}
		}
	}

	cout << "YES" << endl;

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
6
1 2 5 3 4 6
01110

Output

x
–
+
cmd
YES
Advertisements

Demonstration

Codeforces Solution-C. Swap Adjacent Elements-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+