2021-2022 ICPC, Moscow Subregional |
---|
Закончено |
One of the greatest e-sport events, The Invitational TOAD-3 Championship, will feature $$$16$$$ best teams in the world. In order to prolong the fascinating event and acquire more money from advertising a double-elimination tournament scheme will be used.
First, all teams are ordered by their rating and the $$$i$$$-th team in the sorted list plays versus the team at position $$$(17-i)$$$. The winner of each of these matches goes to the winners' bracket, the loser goes to the losers' bracket.
Participants of the winners' bracket continue to play a single-elimination tournament, except that the losers of each round "drop down" into the losers' bracket.
Each round of the loser's bracket is conducted in two stages; a minor stage followed by a major stage. Both contain the same number of matches which is the same again as the number of matches in the corresponding round of the winners' bracket. If the minor stage of a looser's bracket round contains $$$2^k$$$ matches, there will be $$$2^k$$$ winners. Meanwhile, the $$$2^k$$$ matches in the corresponding round of the winners' bracket will produce $$$2^k$$$ losers. These $$$2^{k+1}$$$ teams will then form pairs for $$$2^k$$$ matches of the corresponding major stage of the looser's bracket. At this stage of the round, looser of the winners' bracket round can play only against winners of the minor stage of the looser's bracket.
In both brackets, before each round opponents are chosen at random to form pairs. Same apply to the process of forming pairs of type "loser from winners' bracket versus winner of the minor stage from the losers' bracket" at the major stages of the losers' bracket rounds.
All players who are eliminated from the same stage are considered to share the same position in the resulting ranking.
Below is the scheme of how the double-elimination tournament for 16 teams is held.
You are given the list of teams with the results of all matches played by this team during the tournament in chronological order. Determine the final place for each team.
The input contains $$$16$$$ lines.
Each line consists of two strings — the team name $$$t$$$ made up of lowercase English letters ($$$1 \le |t| \le 50$$$) and the string $$$G$$$ with the outcomes of all games this team has played. String $$$G$$$ consists of digits 1 and 0 only. If the $$$i$$$-th character of this string equals 1 it means that this team won its $$$i$$$-th match on the tournament. If the $$$i$$$-th character of this string equals to 0, it means that this team lost its $$$i$$$-th match on the tournament.
You may assume that all team names are distinct and that the distribution of wins and losses correspond to some correctly held double-elimination tournament for those teams.
Print 16 lines. Each line should contain the notation for place: one integer if the place is not shared, and two integers separated by single '-' — the highest and the lowest if the place is shared, followed by the team name.
Teams shall be listed by their places in increasing order. If several teams share a place, sort those teams by the name lexicographically. See sample output for further clarification.
escmraeett 11100 neigulsievse 010 noet 1010 nduymianegt 00 psimraiett 10111111 ustprriov 1100 yccnrieuwq 010 go 1010 agmiicnigv 10110 ctosaasetb 00 sugtacmiivnngi 11010 hpaenlte 00 lggsdp 11110 taincf 010 ainlclea 010 asmtaeert 00
1 psimraiett 2 lggsdp 3 escmraeett 4 sugtacmiivnngi 5-6 agmiicnigv 5-6 ustprriov 7-8 go 7-8 noet 9-12 ainlclea 9-12 neigulsievse 9-12 taincf 9-12 yccnrieuwq 13-16 asmtaeert 13-16 ctosaasetb 13-16 hpaenlte 13-16 nduymianegt
Название |
---|