题解：CF599B Spongebob and Joke

CyanStd's Blog / 2024-11-05 / 原文

完整题意详见题面。

已知 $b_i=f_{a_i}$，求数组 $a$ 的值。

先记录每个 $f_i$ 的值的数量，

当 $f$ 数组中与 $b$ 数组中没有相同的值时，输出 Impossible
当 $f$ 数组中与 $b$ 数组中有多组相同的值时，输出 Ambiguity
其余情况输出 Possible。

然后考虑如何求出数组 $a$，

对于 $b_i=f_{a_i}$，通过 $f$ 数组记录每一个可能的 $a_i$ 的值。易得，数组 $b$ 的长度与 $a$ 的长度相等。在判断合法后输出 $a_{b_i}$ 即可。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int cnt[100010],b[100010],a[100010];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int f;
		cin>>f;
		cnt[f]++;
		a[f]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
		if(cnt[b[i]]==0){
			cout<<"Impossible";
			return 0;
		}
	}
	for(int i=1;i<=m;i++){
		if(cnt[b[i]]>1){
			cout<<"Ambiguity";
			return 0;
		}
	}
	cout<<"Possible"<<endl;
	for(int i=1;i<=m;i++)
		cout<<a[b[i]]<<' ';
	return 0;
}

点击查看代码

#include<bits/stdc++.h>
using namespace std;
int cnt[100010],b[100010],a[100010];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int f;
		cin>>f;
		cnt[f]++;
		a[f]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>b[i];
		if(cnt[b[i]]==0){
			cout<<"Impossible";
			return 0;
		}
	}
	for(int i=1;i<=m;i++){
		if(cnt[b[i]]>1){
			cout<<"Ambiguity";
			return 0;
		}
	}
	cout<<"Possible"<<endl;
	for(int i=1;i<=m;i++)
		cout<<a[b[i]]<<' ';
	return 0;
}