310080: CF1779H. Olympic Team Building
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Olympic Team Building
题目描述
Iron and Werewolf are participating in a chess Olympiad, so they want to practice team building. They gathered $ n $ players, where $ n $ is a power of $ 2 $ , and they will play sports. Iron and Werewolf are among those $ n $ people. One of the sports is tug of war. For each $ 1\leq i \leq n $ , the $ i $ -th player has strength $ s_i $ . Elimination rounds will be held until only one player remains — we call that player the absolute winner. In each round: - Assume that $ m>1 $ players are still in the game, where $ m $ is a power of $ 2 $ . - The $ m $ players are split into two teams of equal sizes (i. e., with $ m/2 $ players in each team). The strength of a team is the sum of the strengths of its players. - If the teams have equal strengths, Iron chooses who wins; otherwise, the stronger team wins. - Every player in the losing team is eliminated, so $ m/2 $ players remain. Iron already knows each player's strength and is wondering who can become the absolute winner and who can't if he may choose how the teams will be formed in each round, as well as the winning team in case of equal strengths.输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 4 \leq n \leq 32 $ ) — the number of players participating in tug of war. It is guaranteed that $ n $ is a power of $ 2 $ . The second line consists of a sequence $ s_1,s_2, \ldots, s_n $ of integers ( $ 1 \leq s_i \leq 10^{15} $ ) — the strengths of the players.
输出格式
In a single line output a binary string $ s $ of length $ n $ — the $ i $ -th character of $ s $ should be $ 1 $ if the $ i $ -th player can become the absolute winner and it should be $ 0 $ otherwise.
输入输出样例
输入样例 #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说明
In the first example, players $ 1 $ and $ 4 $ with their respective strengths of $ 60 $ and $ 87 $ can become the absolute winners. Let's describe the process for player $ 1 $ . Firstly, we divide the players into teams $ [1,3] $ and $ [2,4] $ . Strengths of those two teams are $ 60+59=119 $ and $ 32+87=119 $ . They they are equal, Iron can choose to disqualify any of the two teams. Let his choice be the second team. We are left with players $ 1 $ and $ 3 $ . Since $ 1 $ has greater strength ( $ 60>59 $ ) they win and are declared the absolute winner as they are the last remaining player. In the third example, the strengths of the remaining players may look like $ [8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8] $ . Each person with strength $ 8 $ can become the absolute winner and it can be proved that others can't.Input
暂时还没有翻译
Output
**奥林匹克团队建设**
**题目描述**
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] → [8,8,4,4] → [8,4] → [8]。每个有8力量的玩家可以成为绝对赢家，可以证明其他人不能。**奥林匹克团队建设** **题目描述** 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] → [8,8,4,4] → [8,4] → [8]。每个有8力量的玩家可以成为绝对赢家，可以证明其他人不能。
**题目描述**
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] → [8,8,4,4] → [8,4] → [8]。每个有8力量的玩家可以成为绝对赢家，可以证明其他人不能。**奥林匹克团队建设** **题目描述** 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] → [8,8,4,4] → [8,4] → [8]。每个有8力量的玩家可以成为绝对赢家，可以证明其他人不能。