CF1779H Olympic Team Building

Iron 和 Werewolf 正在参加国际象棋奥林匹克，因此他们想进行团队建设。他们召集了 $n$ 名选手，其中 $n$ 是 $2$ 的幂，这些人将一起进行体育活动。Iron 和 Werewolf 也在这 $n$ 个人之中。 其中一项运动是拔河比赛。对于每个 $1 \leq i \leq n$，第 $i$ 位选手的力量为 $s_i$。比赛将采用淘汰制，直到只剩下一名选手——我们称这名选手为绝对胜者。 每一轮比赛规则如下： - 假设当前还有 $m>1$ 名选手在比赛中，其中 $m$ 是 $2$ 的幂。 - 这 $m$ 名选手被分成两支人数相等的队伍（即每队 $m/2$ 人）。一支队伍的力量等于其所有成员的力量之和。 - 如果两队力量相等，则由 Iron 选择哪支队伍获胜；否则，力量更强的队伍获胜。 - 所有失败队伍的选手被淘汰，因此剩下 $m/2$ 名选手。 Iron 已经知道每位选手的力量，他想知道，如果他可以自由选择每一轮的分组方式，并且在力量相等时可以选择获胜队伍，哪些选手有可能成为绝对胜者，哪些不可能。

第一行包含一个整数 $n$（$4 \leq n \leq 32$）——参加拔河比赛的选手人数。保证 $n$ 是 $2$ 的幂。 第二行包含一组整数 $s_1,s_2, \ldots, s_n$（$1 \leq s_i \leq 10^{15}$）——每位选手的力量。

输出一行长度为 $n$ 的二进制字符串 $s$——如果第 $i$ 位选手有可能成为绝对胜者，则 $s$ 的第 $i$ 位为 $1$，否则为 $0$。

在第一个样例中，力量分别为 $60$ 和 $87$ 的第 $1$ 和第 $4$ 位选手有可能成为绝对胜者。 以第 $1$ 位选手为例，首先我们可以将选手分为 $[1,3]$ 和 $[2,4]$ 两队。这两队的力量分别为 $60+59=119$ 和 $32+87=119$。由于两队力量相等，Iron 可以选择淘汰任意一队。假设他选择淘汰第二队。 此时只剩下第 $1$ 和第 $3$ 位选手。由于 $1$ 号选手的力量更大（$60>59$），他获胜并成为最后的绝对胜者。 在第三个样例中，剩下的选手力量可能为 $[8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]$。每个力量为 $8$ 的人都可以成为绝对胜者，可以证明其他人不行。 由 ChatGPT 4.1 翻译