# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

**“If you feel unwell, stay home.”**

Riaz has created a special encryption algorithm named Quarantiko to encrypt any array of consisting 0 and 1. He encrypted an array and gave you the encrypted array and the encrypted keys. He gave you a challenge to decrypt it.

You will be given the encrypted array and encrypted keys for every index. You have to find the real array. (Here encrypted key of any index is the Quaran cost between the prefix of encrypted array till this index and the real array).

Suppose, given encrypted array {1, 1, 1, 1, 1} and encrypted keys {4, 3, 3, 3, 2}. Here, 1st key 4 is the Quaran cost between prefix {1} and the real array, 2nd key 3 is the Quaran cost between prefix {1, 1} and the real array and so on.

**Note:** Quaran cost of two arrays A and B is a value equal to the minimum number of one-element operations of replacing any element in A or inserting element at right side in A to get B. For example, the cost between A{1, 0, 1} and B{1, 1, 1} is 1, the cost between A{1, 1} and B{1, 0, 1} is 2, the cost between A{1, 0, 1} and B{0, 1, 0} is 3. The Quaran cost is 0 if and only if the arrays are equal.

The first line will contain a number **N** (1 ≤ **N** ≤ 1e5), the length of arrays.

Next line contains N numbers (0 ≤ **a1, a2…an** ≤ 1), where **ai** represent the **ith** element of encrypted array.

Next line contains N numbers (0 ≤ **c1, c2…cn** ≤ 1e5), where **ci** represent the encrypted key of **ith** index.

N space separated numbers which denotes your real array.

Input | Output |
---|---|

5 1 1 1 1 1 4 3 3 3 2 | 1 1 0 0 1 |

66% Solution Ratio

iammarajulEarliest,

emrul_muFastest, 0.0s

fuadulhasanLightest, 786 kB

Abdullah_SheehanShortest, 396B

Login to submit