# CF1608C「Game Master」

## 1. 题目

### Description

$n$ 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 $n−1$ 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.

### Input

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of players.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$, $a_i \neq a_j$ for $i \neq j$), where $a_i$ is the strength of the $i$-th player on the first map.

The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \leq b_i \leq 10^9$, $b_i \neq b_j$ for $i \neq j$), where $b_i$ is the strength of the $i$-th player on the second map.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

### Output

For each test case print a string of length $n$. $i$-th character should be 1 if the $i$-th player can win the tournament, or 0 otherwise.

### Note

In the first test case, the $4$-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.

## 2. 题解

### 分析

• 但这样存在一个问题，每个 player 能赢的其它 player 可能很多，这样建图的空间复杂度就太高了。可以先按照数组 $a$ 对 player 进行升序排序。这样在有序的数组 $a$ 中，对应数组 $a$ 后面的 player 肯定可以赢它前面的 player，这样只需建立相邻 player 之间的边即可。

• 但还存在另一个问题，如果需要判断每个 player 是否可达 $\max_a$，则时间复杂度又太高了。因此，不妨逆向思考，如果 player $i$ 能够赢 player $j$，则连接一条有向边 $j \rightarrow i$ 的边。然后从 $\max_b$ 开始 BFS，能遍历到的 player 都能胜出，不能遍历到的 player 都无法胜出。