https://codeforces.com/problemset/problem/1608/C
输入 T(≤100) 表示 T 组数据。所有数据的 n 之和 ≤1e5。
每组数据输入 n(≤1e5),长为 n 的数组 a(1≤a[i]≤1e9),长为 n 的数组 b(1≤b[i]≤1e9)。
a 中无重复元素,b 中无重复元素。
有 n 名选手,两个比赛场地。第 i 个选手在第一个场地的力量是 a[i],在第二个场地的力量是 b[i]。
每次从剩余选手中选择两名选手,以及一处比赛场地。力量小的淘汰。
n-1 次比赛后,剩下的那个人是冠军。
安排谁和谁比赛的权力在你手上(你是懂暗箱操作的),
请对每位选手都作出判断,如果第 i 位选手能成为冠军,输出 1,否则输出 0。
输入
3
4
1 2 3 4
1 2 3 4
4
11 12 20 21
44 22 11 30
1
1000000000
1000000000
输出
0001
1111
1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010, M = 2 * N;
PII v[N];
int e[M], ne[M], h[N], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt;
int din[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u;
in_stk[u] = true;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if(in_stk[j])
low[u] = min(low[u], dfn[j]);
}
if(dfn[u] == low[u]){
++ scc_cnt;
int y;
do{
y = stk[top --];
in_stk[y] = false;
id[y] = scc_cnt;
}while(y != u);
}
}
int main ()
{
int T;
cin >> T;
while(T --){
int n;
cin >> n;
memset(h, -1, sizeof h);
timestamp = 0;
scc_cnt = 0;
idx = 0;
memset(din, 0, sizeof din);
memset(id, 0, sizeof id);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
for(int i = 0; i < n; i ++) cin >> v[i].first;
for(int i = 0; i < n; i ++) cin >> v[i].second;
vector<int> ID(n);
for(int i = 0; i < n; i ++) ID[i] = i;
sort(ID.begin(), ID.end(), [&](const auto &a, const auto &b){
return v[a].first < v[b].first;
});
for(int i = 1; i < n; i ++){
int a = ID[i - 1], b = ID[i];
add(b, a);
}
sort(ID.begin(), ID.end(), [&](const auto &a, const auto &b){
return v[a].second < v[b].second;
});
for(int i = 1; i < n; i ++){
int a = ID[i - 1], b = ID[i];
add(b, a);
}
for(int i = 0; i < n; i ++)
if(!dfn[i])
tarjan(i);
for(int u = 0; u < n; u ++)
{
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(id[u] != id[j])
{
din[id[j]] ++;
}
}
}
vector<int> ans(n);
for(int i = 0; i < n; i ++)
{
if(!din[id[i]]) ans[i] = 1;
else ans[i] = 0;
}
for(int i = 0; i < n; i ++) cout << ans[i];
puts("");
}
return 0;
}