本题可以抽象为图论问题:
由题意可知,在两张地图上权值最大的那两个人x
和y
能赢,那么能赢这两个人的也能赢,依次类推,我们根据玩家在两张地图上的权值对玩家的下标进行建图,strength
小的玩家A
指向strength
刚刚大于A
的B
,形成了一棵树,我们对x
和y
进行\(dfs\),能被指向的玩家可以成为赢家。
代码:
#include <bits/stdc++.h>
#define pb push_back
#define LL long long
#define sz(x) (int)x.size()
#define all(s) (s).begin(), (s).end()
using namespace std;
const int N = 200010;
struct athlete{
int x;
int y;
int index;
}a[N];
int n;
int h[N], ne[N], idx, e[N], ans[N], st[N];
bool cmp1(athlete A, athlete B){
return A.x < B.x;
}
bool cmp2(athlete A, athlete B){
return A.y < B.y;
}
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int x){
st[x] = true;
ans[x] = 1;
for(int i = h[x]; i != -1; i = ne[i]){
int y = e[i];
if(!st[y]) dfs(y);
}
}
void solve()
{
scanf("%d",&n);
idx = 0;
for(int i = 1; i <= n; i ++ ){
h[i] = -1;
ans[i] = 0;
st[i] = false;
}
for(int i = 1; i <= n; i ++ ) scanf("%d",&a[i].x);
for(int i = 1; i <= n; i ++ ){
scanf("%d",&a[i].y);
a[i].index = i;
}
sort(a + 1, a + 1 + n, cmp1);
for(int i = 2; i <= n; i ++ ) add(a[i - 1].index, a[i].index);
int xx = a[n].index;
sort(a + 1, a + 1 + n, cmp2);
for(int i = 2; i <= n; i ++ ) add(a[i - 1].index, a[i].index);
dfs(a[n].index);
for(int i = 1; i <= n; i ++ ) st[i] = false;
dfs(xx);
for(int i = 1; i <= n; i ++ ) printf("%d",ans[i]);
printf("\n");
}
int main()
{
int test;
scanf("%d", &test);
while(test -- )
{
solve();
}
return 0;
}