B. Spongebob and Joke
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick’s personal stuff and found a sequence _a_1, _a_2, …, a__m of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence _f_1, _f_2, …, f__n of length n and for each number a__i got number b__i = f__a__i. To finish the prank he erased the initial sequence a__i.
It’s hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.
Input
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) – the lengths of sequences f__i and b__i respectively.
The second line contains n integers, determining sequence _f_1, _f_2, …, f__n (1 ≤ f__i ≤ n).
The last line contains m integers, determining sequence _b_1, _b_2, …, b__m (1 ≤ b__i ≤ n).
Output
Print “Possible” if there is exactly one sequence a__i, such that b__i = f__a__i for all i from 1 to m. Then print m integers_a_1, _a_2, …, a__m.
If there are multiple suitable sequences a__i, print “Ambiguity”.
If Spongebob has made a mistake in his calculations and no suitable sequence a__i exists, print “Impossible”.
Sample test(s)
input
3 3
3 2 1 1 2 3
output
Possible
3 2 1
input
3 3
1 1 1 1 1 1
output
Ambiguity
input
3 3
1 2 1 3 3 3
output
Impossible
Note
In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.
In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.
In the third sample f__i ≠ 3 for all i, so no sequence a__i transforms into such b__i and we can say for sure that Spongebob has made a mistake.
理解题意。。
需要注意的是，只有当在f中重复出现的那个在b中也出现了，答案才是任意；不然无影响。
代码实现
1#include <cstdio>
2#include <iostream>
3#include <cstring>
4#include <algorithm>
5
6const int N=1E5+7;
7int n,m;
8int ans[N];
9bool v[N];
10bool v2[N];
11using namespace std;
12
13struct node
14{
15int val;
16int id;
17}f[N],b[N];
18
19bool cmp( node a,node b)
20{
21return a.val<b.val;
22}
23int main()
24{
25cin>>n>>m;
26memset(v2,false,sizeof(v2));
27for ( int i = 0 ; i < n ; i++) scanf("%d",&f[i].val),f[i].id=i;
28for ( int i = 0 ; i < m ; i++) scanf("%d",&b[i].val),b[i].id=i;
29for ( int i = 0 ; i < m ; i++) v2[b[i].val] = true;
30
31sort(f,f+n,cmp);
32sort(b,b+m,cmp);
33
34bool multi = false;
35memset(v,false,sizeof(v));
36for ( int i = 0 ; i < n-1 ; i++) if (f[i].val==f[i+1].val&&v2[f[i+1].val]) multi = true;
37for ( int i = 0 ; i < n ; i++) v[f[i].val] = true;
38bool sad = false;
39for ( int i = 0 ; i < m; i++) if (!v[b[i].val]) sad = true;
40memset(ans,0,sizeof(ans));
41int j = 0;
42bool flag = false;
43for ( int i = 0 ; i < n ; i++)
44{
45if (j==m) break;
46if (f[i].val==b[j].val&&j<m)
47{
48while (f[i].val==b[j].val&&j<m)
49{
50ans[b[j].id] = f[i].id;
51j++;
52}
53}
54
55}
56if (sad)
57{
58puts("Impossible");
59}
60else
61{
62if (multi) puts("Ambiguity");
63else
64{
65puts("Possible");
66for ( int i = 0 ; i < m-1 ; i++)
67printf("%d ",ans[i]+1);
68printf("%dn",ans[m-1]+1);
69}
70
71}
72
73
74
75
76}