P14520 【MX-S11-T1】战争游戏

小 L 和小 K 发明了一种新的游戏。游戏将在一行 $n$ 个格子上进行，代表 $n$ 个城市，分别为城市 $1,2,\dots,n$。初始，城市 $i$ 有士兵 $a_i$ 人。两人约定，前 $m$ 个编号的城市是小 L 的地盘，其他城市是小 K 的地盘。 两人将交替进行操作，小 L 先手。轮到该方操作时，可以作出如下行动之一： - 转移：选择己方地盘上的两个城市 $x,y$，满足 $|x-y|=1$，把城市 $x$ 的士兵全部转移到城市 $y$，即同时令 $a_y\leftarrow a_x+a_y$，$a_x\leftarrow 0$。 - 攻占：选择己方地盘上的城市 $x$ 和对方地盘上的城市 $y$，满足 $|x-y|=1$ 且轮到小 L 操作时需满足 $a_x>a_y$，轮到小 K 操作时需满足 $a_x\geq a_y$，攻占对方的城市 $y$，把城市 $x$ 的士兵全部转移到城市 $y$，即同时令 $a_y\leftarrow a_x+a_y$，$a_x\leftarrow 0$，把城市 $y$ 归到己方的地盘上。 - 不进行任何操作。 当一方将所有城市归为己方地盘时，该方获胜。如果两人都绝顶聪明的话，谁将获胜？请你对于 $m=1,2,\dots,n-1$ 分别输出 $m$ 取该值时问题的答案。 可以证明在双方绝顶聪明的情况下，博弈一定可以在有限次操作内结束。

**本题包含多组测试数据。** 第一行，一个正整数 $T$，表示测试数据组数。对于每组测试数据： - 第一行，一个正整数 $n$，表示城市数量。 - 第二行，$n$ 个正整数 $a_1, \ldots, a_n$，表示每个城市的士兵数量。

对于每组测试数据，一行一个长度为 $n-1$ 的 `01` 字符串 $S$，分别表示 $m=1,2,\dots,n-1$ 时的答案。对于每一个 $m$，若小 L 获胜，输出 `1`，否则输出 `0`。

**【样例解释 #1】** 初始 $a=\{4,3,1,6,3,4,1\}$。 当 $m=1$ 时，小 L 的最优策略是选择攻占操作，取 $x=1$ 和 $y=2$，这次操作后序列 $a=\{0,7,1,6,3,4,1\}$，城市 $2$ 归到小 L 的地盘上。接下来，小 K 只需不断地选择转移操作，把第 $3$ 个城市往后的所有士兵经过 $4$ 轮都转移到第 $7$ 个城市，此时 $a_7=15$，小 L 一方无论如何最多只可能有 $7$ 个士兵。小 K 无论如何都能取得胜利。 当 $m=4$ 时，小 L 只需要把第 $4$ 个城市向前的所有士兵经过 $3$ 轮都转移到城市 $1$，此时 $a_1=14$，对方最多只可能有 $8$ 个士兵。小 L 无论如何都能取得胜利。 **【样例 #2】** 见选手目录下的 $\textbf{\textit{war/war2.in}}$ 与 $\textbf{\textit{war/war2.ans}}$。 该样例满足测试点 $1$ 的约束条件。 **【样例 #3】** 见选手目录下的 $\textbf{\textit{war/war3.in}}$ 与 $\textbf{\textit{war/war3.ans}}$。 该样例满足测试点 $4\sim 7$ 的约束条件。 **【样例 #4】** 见选手目录下的 $\textbf{\textit{war/war4.in}}$ 与 $\textbf{\textit{war/war4.ans}}$。 该样例满足测试点 $11\sim 13$ 的约束条件。 **【样例 #5】** 见选手目录下的 $\textbf{\textit{war/war5.in}}$ 与 $\textbf{\textit{war/war5.ans}}$。 该样例满足测试点 $14\sim 18$ 的约束条件。 **【样例 #6】** 见选手目录下的 $\textbf{\textit{war/war6.in}}$ 与 $\textbf{\textit{war/war6.ans}}$。 该样例满足测试点 $19\sim 25$ 的约束条件。 **【数据范围】** 本题共 $25$ 个测试点，每个 $4$ 分。 对于所有测试数据，保证： - $1\le T\le 20$； - $2\leq n\leq10^5$； - $1\leq a_i\leq10^9$。 ::cute-table{tuack} | 测试点编号 | $n \le$ | 特殊性质| | :----------: | :----------: | :-----:| | $1$ | $2$ | 无 | | $2, 3$ | $4$ | ^ | | $4\sim 7$ | $10$ | ^ | | $8\sim 10$ | $10^5$ | A | | $11\sim 13$ | ^ | B | | $14\sim 18$| ^ | C | | $19\sim 25$ | ^ | 无 | 特殊性质 A：对于所有 $1 \le i \le n$ 均有 $a_i=1$。 特殊性质 B：对于所有 $1 \le i < n$ 均有 $a_i\leq a_{i+1}$。 特殊性质 C：对于所有 $1 \le i \le n - 2$ 均有 $a_i+a_{i+1}> a_{i+2}$。