codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

599B.md (2331B)


      1 Source: https://codeforces.com/problemset/problem/599/B
      2 
      3 B. Spongebob and Joke
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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*.
     22 
     23 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.
     24 
     25 Input
     26 
     27 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.
     28 
     29 The second line contains *n* integers, determining sequence *f*1, *f*2, ..., *f**n* (1 ≤ *f**i* ≤ *n*).
     30 
     31 The last line contains *m* integers, determining sequence *b*1, *b*2, ..., *b**m* (1 ≤ *b**i* ≤ *n*).
     32 
     33 Output
     34 
     35 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*.
     36 
     37 If there are multiple suitable sequences *a**i*, print "Ambiguity".
     38 
     39 If Spongebob has made a mistake in his calculations and no suitable sequence *a**i* exists, print "Impossible".
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3 3  
     47 3 2 1  
     48 1 2 3
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 Possible  
     55 3 2 1
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 3 3  
     62 1 1 1  
     63 1 1 1
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 Ambiguity
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 3 3  
     76 1 2 1  
     77 3 3 3
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 Impossible
     84 ```
     85 
     86 Note
     87 
     88 In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.
     89 
     90 In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.
     91 
     92 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.