Codeforces Round 645 (Div. 2) |
---|
Закончено |
О нет!
Вас поймал коронавирус, и теперь вы сидите в тёмном подвале, связанные по ногам (но не по рукам). У вас есть вкусная печенька, а также перед вами стоит ноутбук, и там открыта ваша любимая среда разработки. Коронавирус убеждает вас решить следующую задачу.
Вам дано два массива $$$A$$$ и $$$B$$$ размера $$$n$$$. Вы можете делать операции двух типов с массивом $$$A$$$:
Вам нужно понять, можно ли из массива $$$A$$$ получить массив $$$B$$$. Если это можно сделать, то вам придётся восстановить порядок этих операций, минимизировав количество операций второго типа. К счастью, коронавирус сегодня добрый, поэтому он разрешил вам не восстанавливать действия, если минимальное количество операций второго типа превышает $$$2\cdot 10^5$$$. Но коронавирус обижен на вас, поэтому если вы восстанавливаете ответ, то суммарное количество операций не должно превышать $$$5\cdot 10^5$$$.
Решите эту задачу, или коронавирус продлит карантин на пять лет и заставит всю экономику рухнуть!
В первой строке входных данных вводится число $$$n$$$ ($$$1\le n \le 2\cdot 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$A_1, A_2, \ldots, A_n$$$ ($$$1 \le A_i \le 10 ^ {12}$$$).
Третья строка содержит $$$n$$$ целых чисел $$$B_1, B_2, \ldots, B_n$$$ ($$$1 \le B_i \le 10 ^ {12}$$$).
Если из массива $$$A$$$ нельзя получить массив $$$B$$$, в единственной строке выведите «IMPOSSIBLE» (без кавычек).
Если минимальное количество операций второго типа превышает $$$2\cdot 10^5$$$, то в первой строке выведите «BIG» (без кавычек). Во второй строке выведите минимальное количество операций второго типа, которые нужно применить, чтобы из массива $$$A$$$ получить $$$B$$$.
Иначе, в первой строке выведите «SMALL» (без кавычек). Во второй строке выведите суммарное количество операций первого и второго типа $$$m \le 5\cdot 10^5$$$ (гарантируется, что в этом случае существует такая последовательность действий). В третьей строке выведите строку длины $$$m$$$, состоящую из символов «R» и «P» (без кавычек):
$$$i$$$-й символ должен быть равен 'R', если $$$i$$$-е действие первого типа, и должен быть равен 'P', иначе.
Если таких последовательностей несколько, выведите любую из них.
Вы можете выводить все символы как в нижнем регистре, так и в верхнем.
2 5 7 5 7
SMALL 0
2 1 1 300000 1
BIG 299999
2 10 1 13 14
SMALL 6 RPPPRP
3 1 2 1 2 1 2
IMPOSSIBLE
В первом примере массивы $$$A$$$ и $$$B$$$ уже совпадает, поэтому количество нужных операций $$$=0$$$.
Во втором примере надо $$$299999$$$ раз заменить $$$A$$$ на префиксную сумму, а потом развернуть массив. Так как $$$299999>2\cdot 10^5$$$, то восстанавливать ответ не нужно.
В четвёртом примере из массива $$$A$$$ никак нельзя получить $$$B$$$.
Название |
---|