P14048 [SDCPC 2019] Heap

DreamGrid 正在数据结构课上学习堆的插入操作。 在下面的描述中，我们将 $i/2$ 记作满足 $2x \le i$ 的最大整数 $x$。回忆如下内容： - 一个大小为 $n$ 的堆是一个数组 $a_1, a_2, \dots, a_n$，其满足以下两个条件之一： - 对于所有 $2 \le i \le n$，都有 $a_{i/2} \le a_i$。这称为小根堆。 - 对于所有 $2 \le i \le n$，都有 $a_{i/2} \ge a_i$。这称为大根堆。 - 插入操作可描述为如下伪代码： :::align{center}  ::: DreamGrid 准备了一个初始为空的堆数组 $a$ 和 $n$ 个整数 $v_1, v_2, \dots, v_n$。他正准备依次把这 $n$ 个整数插入堆数组，这时手机响了，于是他把这项工作交给室友 BaoBao 去做。 不幸的是，BaoBao 并不理解插入函数参数 $is\_max$ 的意义（不过亲爱的参赛者，你一定已经理解了这个参数的含义），于是他生成了一个长度为 $n$ 的二进制串（只包含 `0` 和 `1` 的字符串）$b = b_1b_2\dots b_n$，其中 $b_i$ 表示串中的第 $i$ 个字符，并且他根据这个字符串决定 $is\_max$ 的值。在插入 $v_i$ 时，若 $b_i$ 等于 `0`，则此次插入中的 $is\_max$ 为假；否则如果 $b_i$ 等于 `1`，此次插入中的 $is\_max$ 为真。 当 DreamGrid 回来后，发现最终的“堆”数组 $a_1, a_2, \dots, a_n$ 似乎并不是一个有效的堆！给定依次插入的 $n$ 个整数 $v_1, v_2, \dots, v_n$ 以及最终的数组，并已知 BaoBao 是按照顺序插入 $v_1, v_2, \dots, v_n$ 的，请你帮助 DreamGrid 恢复出 BaoBao 生成的二进制串 $b$。

有多组测试数据。输入的第一行包含一个整数 $T$，表示测试数据组数。对于每组测试数据： 第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示最终数组的大小。 第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$（$1 \le v_i \le 10^9$），表示依次插入的整数。 第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，是 $v_1, v_2, \dots, v_n$ 的一个排列，表示最终“堆”的数组。 保证所有测试数据中 $n$ 的总和不超过 $10^6$。

对于每组测试数据，输出一行一个二进制字符串，表示用于插入的二进制串。如果存在多个合法答案，输出字典序最小的那个。如果不存在这样的二进制串，则输出 `Impossible`（不含引号）。 回忆：对于长度为 $n$ 的两个二进制串 $s$ 和 $t$，我们称 $s$ 的字典序小于 $t$，当存在整数 $k$ 满足所有下列条件时： - $1\le k\le n$。 - 对于所有 $1\le i

下面解释第一个样例： $$\begin{array}{|c|c|c|c|} \hline \textbf{$i$} & \textbf{$v_i$} & \textbf{$b_i$} & \textbf{插入后 “堆” 数组} \\ \hline 1 & 2 & 0 & \{2\} \\ \hline 2 & 3 & 1 & \{3, 2\} \\ \hline 3 & 1 & 0 & \{1, 2, 3\} \\ \hline 4 & 4 & 1 & \{4, 1, 3, 2\} \\ \hline \end{array}$$ 由 ChatGPT 5 翻译