CF1659D Reverse Sort Sum

假设你有一个长度为 $n$ 的数组 $A$，其中每个元素都是 $0$ 或 $1$。 我们定义一个函数 $f(k, A)$，它返回另一个数组 $B$，即将 $A$ 的前 $k$ 个元素按非递减顺序排序后的结果。例如，$f(4, [0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]$。注意，只有前 $4$ 个元素被排序了。 现在考虑由 $f(1, A), f(2, A), \ldots, f(n, A)$ 生成的数组 $B_1, B_2, \ldots, B_n$。令 $C$ 为将 $B_1, B_2, \ldots, B_n$ 按位相加得到的数组。 例如，设 $A=[0,1,0,1]$。那么有 $B_1=[0,1,0,1]$，$B_2=[0,1,0,1]$，$B_3=[0,0,1,1]$，$B_4=[0,0,1,1]$。于是 $C=B_1+B_2+B_3+B_4=[0,1,0,1]+[0,1,0,1]+[0,0,1,1]+[0,0,1,1]=[0,2,2,4]$。 现在给定 $C$，请你求出一个二进制数组 $A$，使得按照上述过程处理后能得到 $C$。保证输入的 $C$ 一定存在对应的 $A$。

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例包含两行。第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$0 \leq c_i \leq n$）。保证对于给定的 $C$，一定存在一个合法的数组 $A$。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行，包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$a_i$ 为 $0$ 或 $1$）。如果有多组答案，输出任意一组均可。

以下是第一个测试用例的解释。给定 $A=[1,1,0,1]$，我们可以构造每个 $B_i$： - $B_1=[\color{blue}{1},1,0,1]$； - $B_2=[\color{blue}{1},\color{blue}{1},0,1]$； - $B_3=[\color{blue}{0},\color{blue}{1},\color{blue}{1},1]$； - $B_4=[\color{blue}{0},\color{blue}{1},\color{blue}{1},\color{blue}{1}]$ 然后，将上述每一列相加得到 $C=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4]$。 由 ChatGPT 4.1 翻译