ZOJ Problem Set - 4119
DreamGrid is learning the insertion operation of a heap in the data structure course.
In the following description, we denote $i/2$ to be the maximum integer $x$ that $2x \le i$. Recall that
DreamGrid has prepared an initially empty array $a$ as the heap array and $n$ integers $v_1, v_2, \dots, v_n$. He is just about to insert these $n$ integers into the heap array in order when his cellphone rings, so he leaves this work to his roommate BaoBao.
Unfortunately, BaoBao doesn't understand what the argument $is\_max$ means in the insertion function (but for our dear contestants, we hope that you've understood the meaning of this argument), so he generates a binary string (a string which only contains '0' and '1') $b = b_1b_2\dots b_n$ of length $n$, where $b_i$ indicates the $i$-th character in the string, and decides the value of $is\_max$ according to the string. When inserting $v_i$ into $a$, if $b_i$ equals to '0', then $is\_max$ during this insertion will be false; otherwise if $b_i$ equals to '1', then $is\_max$ during this insertion will be true.
When DreamGrid comes back, he finds with dismay that the final "heap" array $a_1, a_2 \dots, a_n$ does not seem to be a valid heap! Given the $n$ inserted integers $v_1, v_2, \dots, v_n$, the final array and given that BaoBao has inserted $v_1, v_2, \dots, v_n$ in order, please help DreamGrid restore the binary string $b$ BaoBao generates.
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the size of the final array.
The second line contains $n$ integers $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 10^9$), indicating the integers in the order they are inserted.
The third line contains $n$ integers $a_1, a_2, \dots, a_n$, which is a permutation of $v_1, v_2, \dots, v_n$, indicating the final "heap" array.
It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.
For each test case output one line containing one binary string, indicating the string BaoBao generates for inserting the integers. If there are multiple valid answers, output the one with the smallest lexicographic order. If the binary string does not exist, output "Impossible" (without quotes) instead.
Recall that, for two binary strings $s$ and $t$ of length $n$, we say $s$ is lexicographically smaller than $t$, if there exists an integer $k$ satisfying all the following constraints:
3 4 2 3 1 4 4 1 3 2 5 4 5 1 2 3 3 4 1 5 2 3 1 1 2 2 1 1
0101 Impossible 001
We now explain the first sample test case.
Author: WENG, Caizhi
Source: The 10th Shandong Provincial Collegiate Programming Contest