players are playing a game.
There are two different maps in the game. For each player, we know his strength on each map. When two players fight on a specific map, the player with higher strength on that map always wins. No two players have the same strength on the same map.
You are the game master and want to organize a tournament. There will be a total of battles. While there is more than one player in the tournament, choose any map and any two remaining players to fight on it. The player who loses will be eliminated from the tournament.
In the end, exactly one player will remain, and he is declared the winner of the tournament. For each player determine if he can win the tournament.
The first line contains a single integer () — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer () — the number of players.
The second line of each test case contains integers (, for ), where is the strength of the -th player on the first map.
The third line of each test case contains integers (, for ), where is the strength of the -th player on the second map.
It is guaranteed that the sum of over all test cases does not exceed .
For each test case print a string of length . -th character should be
1 if the -th player can win the tournament, or
In the first test case, the -th player will beat any other player on any game, so he will definitely win the tournament.
In the second test case, everyone can be a winner.
In the third test case, there is only one player. Clearly, he will win the tournament.
考虑为有向图的可达性问题。首先简单思考一下，如果 player 能够赢 player ，则连接一条有向边 的边。那么，如果一个 player 最后能胜出，则它必定可达第一个地图中最强的那个 player，不妨记为 （或者是第二个地图中最强的那个 player）。因此，只需判断 是否可达 即可。
- 但这样存在一个问题，每个 player 能赢的其它 player 可能很多，这样建图的空间复杂度就太高了。可以先按照数组 对 player 进行升序排序。这样在有序的数组 中，对应数组 后面的 player 肯定可以赢它前面的 player，这样只需建立相邻 player 之间的边即可。
- 但还存在另一个问题，如果需要判断每个 player 是否可达 ，则时间复杂度又太高了。因此，不妨逆向思考，如果 player 能够赢 player ，则连接一条有向边 的边。然后从 开始 BFS，能遍历到的 player 都能胜出，不能遍历到的 player 都无法胜出。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！