CF1608C「Game Master」

1. 题目

题目链接：CF1608C「Game Master」。

Description

nn 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−1n−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 tt (1≤t≤1001 \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 nn (1≤n≤1051 \leq n \leq 10^5) — the number of players.

The second line of each test case contains nn integers a1,a2,…,ana_1, a_2, \dots, a_n (1≤ai≤1091 \leq a_i \leq 10^9, ai≠aja_i \neq a_j for i≠ji \neq j), where aia_i is the strength of the ii-th player on the first map.

The third line of each test case contains nn integers b1,b2,…,bnb_1, b_2, \dots, b_n (1≤bi≤1091 \leq b_i \leq 10^9, bi≠bjb_i \neq b_j for i≠ji \neq j), where bib_i is the strength of the ii-th player on the second map.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5.

Output

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

Example

input #1

1
2
3
4
5
6
7
8
9
10
3
4
1 2 3 4
1 2 3 4
4
11 12 20 21
44 22 11 30
1
1000000000
1000000000

output #1

1
2
3
0001
1111
1

Note

In the first test case, the 44-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 ii 能够赢 player jj，则连接一条有向边 i→ji \rightarrow j 的边。那么，如果一个 player ii 最后能胜出，则它必定可达第一个地图中最强的那个 player，不妨记为 max⁡a\max_a（或者是第二个地图中最强的那个 player）。因此，只需判断 ii 是否可达 max⁡a\max_a 即可。

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

同样，对数组 bb 也进行相同处理。排序，连接有向边。这样，整个有向图就建立出来了。

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

这样，整道题就解完了，时间复杂度为 O(nlog⁡n)O(n \log{n})，即取决于排序。

代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define ll int
#define MAXN 200005

using namespace std;

struct Point {
    ll idx;     // 索引
    ll a, b;    // 对应于 a, b 数组中的值
};

bool compa(Point p1, Point p2) {
    return p1.a < p2.a;
}

bool compb(Point p1, Point p2) {
    return p1.b < p2.b;
}

// 前向星
struct Edge {
    ll to, next;
};

Point p[MAXN];
ll cnt;
ll head[MAXN];
Edge e[2*MAXN];
ll ans[MAXN];


void init(ll n) {
    cnt = 0;
    memset(head, -1, sizeof(ll)*(n+1));
    memset(ans, 0, sizeof(ll)*(n+1));
}

void add_edge(ll u, ll v) {
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

int main()
{
    ll t;
    scanf("%d", &t);
    
    for(ll i = 0; i < t; ++i) {
        ll n;
        scanf("%d", &n);
        init(n);
        for(ll j = 0; j < n; ++j) {
            p[j].idx = j;
        }
        for(ll j = 0; j < n; ++j) {
            scanf("%d", &p[j].a);
        }
        for(ll j = 0; j < n; ++j) {
            scanf("%d", &p[j].b);
        }
        // sort by a
        sort(p, p+n, compa);
        for(ll j = n-2; ~j; --j) {
            add_edge(p[j].idx, p[j+1].idx);
        }
        // sort by b
        sort(p, p+n, compb);
        for(ll j = n-2; ~j; --j) {
            add_edge(p[j].idx, p[j+1].idx);
        }
        queue <ll> q;
        q.push(p[n-1].idx);
        ans[p[n-1].idx] = 1;
        while(!q.empty()) {
            ll u = q.front();
            q.pop();
            for(ll j = head[u]; j != -1; j = e[j].next) {
                ll v = e[j].to;
                if(!ans[v]) {
                    ans[v] = 1;
                    q.push(v);
                }
            }
        }
        // result
        for(ll j = 0; j < n; ++j) {
            printf("%d", ans[j]);
        }
        printf("\n");
    }
    return 0;
}