CF1349E Slime and Hats

Slime 和 Orac 正在进行一个回合制游戏。在一个大房间里，有 $n$ 个玩家坐在椅子上，面朝前方排成一列，每个人都被分配了一个编号：玩家 $1$ 坐在队伍的最前面，玩家 $2$ 紧挨着他坐在后面，玩家 $3$ 紧挨着玩家 $2$ 坐在后面，依此类推，玩家 $n$ 坐在玩家 $n-1$ 的后面。每个玩家都戴着一顶帽子，帽子的颜色要么是黑色，要么是白色。由于每个玩家都面朝前方，只有当 $i > j$ 时，玩家 $i$ 才能知道玩家 $j$ 的帽子颜色。 每一回合开始时，Orac 会告知房间里是否存在戴黑帽子的玩家。 在 Orac 说完后，如果某个玩家能够唯一确定自己帽子的颜色，他就会把帽子放在椅子上，站起来离开房间。所有玩家都很聪明，如果他们能够通过本回合及之前回合获得的信息推断出自己帽子的颜色，他们就会明白。 在每一回合中，所有知道自己帽子颜色的玩家会同时离开，也就是说，只有在某人本回合离开后，其他人才有可能在下一回合得知自己的帽子颜色并离开。 注意，玩家离开时会把帽子留在椅子上，因此在他前面的玩家仍然无法看到他的帽子。 第 $i$ 个玩家会知道在 $1,2,\ldots,i-1$ 号玩家中具体有哪些人已经离开，以及在 $i+1,i+2,\ldots,n$ 号玩家中有多少人已经离开。 Slime 站在室外，他观察玩家们离开并记录下玩家编号和他们离开的时间。不幸的是，Slime 太粗心了，他只记录了部分数据，数据的格式为“玩家 $x$ 在第 $y$ 回合离开”。 Slime 让你帮他推断每个玩家帽子的颜色。如果有多种方案，输出任意一种即可。

第一行包含一个整数 $n\ (1\le n\le 200\,000)$。 第二行包含 $n$ 个整数 $t_1,t_2,\dots,t_n\ (0\le t_i\le 10^{15})$。如果 $t_i=0$，表示没有关于第 $i$ 个玩家的信息；否则表示第 $i$ 个玩家在第 $t_i$ 回合离开。 保证输入数据至少有一种合法解。

输出一个长度为 $n$ 的二进制字符串。第 $i$ 个字符为 '1' 表示第 $i$ 个玩家戴的是黑帽子，为 '0' 表示戴的是白帽子。如果有多种方案，输出任意一种即可。

在第一个样例中，所有玩家都戴白帽子。第一回合，Orac 告诉所有玩家房间里没有黑帽子，因此每个人都知道自己戴的是白帽子，于是都在第一回合离开。 在第二个样例中，第 $5$ 个玩家戴黑帽子，其余玩家戴白帽子。Orac 告诉所有玩家房间里存在黑帽子，玩家 $5$ 知道其他人都戴白帽子，因此他能推断自己戴的是黑帽子，于是在第一回合离开，其余玩家在第二回合离开。注意，其他玩家在第 $5$ 个玩家离开后可以立即推断自己戴的是白帽子，但根据规则，他们必须等到下一回合才能离开。 在第三个样例中，没有关于游戏的信息，因此输出任意结果都可以。 由 ChatGPT 4.1 翻译