Problem B
Hard Drive

Pia is getting ready for her flight to the NWERC 2018 in Eindhoven. As she is packing her hard drive, she remembers the airline’s ridiculous weight restrictions, which may pose a problem. You see, the hard drive is essentially a string of ones and zeros, and its weight depends on the number of “bit changes” in it: for any two adjacent bits storing two different values, the hard drive gets slightly heavier, so Pia cannot just store arbitrary information on it.

To make matters worse, the drive is so old that some bits are already broken and will always store zeros. The first bit will never be broken, but the last bit will always be.

Pia decides to treat this situation as a challenge: she is now trying to modify the information on the hard drive so that it has exactly the maximum number of bit changes permitted by the airline. However, the broken bits make this harder than expected, so she needs your help.

Find a bit pattern which can be stored on the hard drive and has exactly the desired number of bit changes.


The input consists of:

  • One line with three integers $n$, $c$, and $b$ ($2 \leq n \leq 5\cdot 10^5$, $1 \leq c, b \le n-1$), the size of the hard drive in bits, the desired amount of bit changes, and the number of broken bits. The positions on the hard drive are numbered from $1$ to $n$.

  • One line with $b$ integers $z_1, \ldots , z_ b$ ($2 \leq z_1 < z_2 < \ldots < z_ b = n$), the positions of the broken bits on the hard drive.


Output a bit string of length $n$, representing Pia’s hard drive and containing exactly $c$ bit changes. If there are multiple valid solutions, you may output any one of them. It is guaranteed that at least one solution exists.

Sample Input 1 Sample Output 1
5 2 3
2 3 5
Sample Input 2 Sample Output 2
7 4 2
2 7

Please log in to submit a solution to this problem

Log in