AT_abc392_c 题解

getchar_unlocked · 2025-02-09 21:42:02 · 题解

题目传送门

思路

使用数组 A 映射每个 bib 盯着的人的人，映射第 i 个人即为 A_{Q_i}=i，则 A_i 表示第 i 个穿着 bib 的人的编号。再找到找到这个人正在盯着的人，即 P_{A_i}。最后找到被盯着的人的 bib 编号 Q_{P_{A_i}} 即为所求。

时间复杂度 \mathcal{O}(N)。

实现

令 A_{Q_i}=i，答案即为 Q_{P_{A_i}}。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=3e5+10;
int p[N],q[N],a[N];
signed main(){
    int n=read();
    for(int i=1;i<=n;++i)
        p[i]=read();
    for(int i=1;i<=n;++i){
        q[i]=read();
        a[q[i]]=i;
    }
    for(int i=1;i<=n;++i)
        printf("%d ",q[p[a[i]]]);
    printf("\n");
    return 0;
}