Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Задача : Спанч Боб и шутка
- Пока Патрик бегал по магазинам, Спанч Боб решил немного подшутить над своим другом. Порывшись в его вещах, проказник обнаружил последовательность a1, a2, ..., am длины m, составленную из целых чисел от 1 до n, не обязательно различных. Далее Спанч Боб придумал последовательность f1, f2, ..., fn длины n и получил для каждого числа ai число bi = fai. Исходную последовательность Спанч Боб, разумеется, стёр.
- Сложно передать словами, как же расстроился Патрик когда вернулся из магазина! Скажем лишь, что Спанч Боб быстро пожалел о содеянном и пытается восстановить исходную последовательность. Помогите ему это сделать или определите, что это невозможно.
- Входные данные
- В первой строке входных данных находятся два целых числа n и m (1 ≤ n, m ≤ 100 000) — длины последовательностей fi и bi соответственно.
- Во второй строке содержатся n целых чисел, определяющих последовательность f1, f2, ..., fn (1 ≤ fi ≤ n).
- В последней строке записаны m целых чисел, определяющих последовательность b1, b2, ..., bm (1 ≤ bi ≤ n).
- Выходные данные
- Если существует ровно одна последовательность ai, такая что bi = fai для всех i от 1 до m, то выведите "Possible". Далее выведите m целых чисел a1, a2, ..., am.
- Если существует несколько подходящих последовательностей ai, то выведите "Ambiguity".
- Если Спанч Боб ошибся в своих вычислениях, и ни одной подходящей последовательности ai не существует, то выведите "Impossible".
- Примеры тестов
- входные данные
- 3 3
- 3 2 1
- 1 2 3
- выходные данные
- Possible
- 3 2 1
- входные данные
- 3 3
- 1 1 1
- 1 1 1
- выходные данные
- Ambiguity
- входные данные
- 3 3
- 1 2 1
- 3 3 3
- выходные данные
- Impossible
- Примечание
- В первом примере 3 заменяется на 1 и наоборот, а 2 никогда не изменяется. Ответ существует, и он единствененный.
- Во втором примере все числа заменяются на единицу, поэтому однозначно восстановить исходную последовательность невозможно.
- В третьем примере fi ≠ 3 для всех i, поэтому никакая последовательность ai не перейдёт в такую bi и можно точно сказать, что Спанч Боб где-то ошибся.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement