Practice on Toph

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


By Riaz_BSMRSTU · Limits 2s, 512 MB

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


1 1 1 1 1
4 3 3 3 2

1 1 0 0 1 



66% Solution Ratio

iammarajulEarliest, 1M ago

emrul_muFastest, 0.0s

fuadulhasanLightest, 786 kB

Abdullah_SheehanShortest, 396B


Login to submit