← 返回题目列表

Codeforces · 1779/H

H. 奥运团队建设

中文机器翻译题面 查看原题

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$$$。

示例

输入 #1

4
60 32 59 87

输出 #1

1001

输入 #2

4
100 100 100 100

输出 #2

1111

输入 #3

8
8 8 8 8 4 4 4 4

输出 #3

11110000

输入#4

32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

输出#4

00000000000000001111111111111111

输入 #5

16
1 92875987325987 1 1 92875987325986 92875987325985 1 92875987325988 92875987325990 92875987325989 1 1 92875987325984 92875987325983 1 1

输出 #5

0100110111001000

注意

在第一个例子中,玩家$$$1$$$和$$$4$$$的实力分别为$$$60$$$和$$$87$$$可以成为绝对的赢家。

让我们描述一下玩家 $$$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$$$实力的人都可以成为绝对的胜利者,并且可以证明其他人不能。