Если увлечься темой кодирования информации, можно поймать себя на придумывании совершенно неожиданных алгоритмов. Сегодня вам предстоит разобраться в кодировании массива стеком.
Изначально вам дан пустой стек и пустой массив. Кодом массива $$$a$$$ назовем последовательность действий вида
Например, при выполнении последовательности действий $$$\mathtt{push}(1)$$$, $$$\mathtt{push}(2)$$$, $$$\mathtt{print}$$$, $$$\mathtt{print}$$$, $$$\mathtt{pop}$$$ и $$$\mathtt{print}$$$ в массив оказываются выписаны числа $$$[1, 2, 1, 2, 1]$$$, а на стеке остается лежать только число $$$1$$$. То есть такая последовательность является кодом массива $$$[1, 2, 1, 2, 1]$$$ длины $$$6$$$.
Вам дан массив $$$a$$$ и $$$q$$$ запросов: какой у отрезка массива $$$a$$$ с $$$l_i$$$-го по $$$r_i$$$-й элемент включительно минимальный по количеству действий со стеком код?
Найдите для каждого запроса код соответствующего отрезка массива. Не требуется найти код наименьшей возможной длины, но чем меньше найденный код, тем больше баллов получит ваше решение.
В первой строке ввода даны четыре целых числа $$$n$$$ и $$$q$$$ — длина массива $$$a$$$, про отрезки которого спрашивается в запросах, количество запросов, а также максимальный балл за тест и параметр $$$\gamma$$$, указанный в системе оценивания, которые ваше решение может игнорировать $$$(1 \le n \le 2000$$$; $$$1 \le q \le 10^4$$$).
Во второй строке перечислены $$$n$$$ целых чисел $$$a_i$$$ — элементы массива $$$a$$$ ($$$1 \le a_i \le 10^9$$$).
В $$$i$$$-й из следующих $$$q$$$ строк даны два целых числа $$$l_i$$$ и $$$r_i$$$ — границы отрезка из $$$i$$$-го запроса ($$$1 \le l_i \le r_i \le n$$$).
Для каждого запроса выведите в отдельной строке целое число $$$k$$$ от $$$1$$$ до $$$n + 1$$$ — количество действий в вашем коде соответствующего отрезка массива, после чего в следующей строке выведите через пробел $$$k$$$ целых чисел, описывающих эти действия в порядке их выполнения:
Если в результате выполнения выведенных действий происходит попытка снять число с вершины пустого стека или в конце не получается массив, равный заданному отрезку массива $$$a$$$, ваше решение получает вердикт Wrong Answer. Также вы получите вердикт Wrong Answer, если в вашем коде будет больше $$$n + 1$$$ действия.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач пройдены с положительным вердиктом. То есть, если вы получаете вердикт WA на каком-либо тесте в группе, вы получаете $$$0$$$ баллов за всю группу. Если все тесты группы пройдены с положительным вердиктом, вы получаете сумму баллов за все тесты в группе.
Для каждой подзадачи даны общие для тестов этой подзадачи ограничения и параметр $$$\gamma$$$, показывающий, насколько близкое к ответу жюри решение будет засчитываться на ненулевой балл.
Если ваше решение для $$$i$$$-го запроса в конкретном тесте строит код из $$$p_i$$$ действий, а решение жюри строит код из $$$j_i$$$ действий, то за этот тест ваше решение получает $$$$$$\max\left(0, \mathtt{score} - \max\left(0, \max\limits_{i=1}^q \left\lfloor\frac{p_i - j_i}{\gamma}\right\rfloor\right)\right) \text{ баллов,}$$$$$$ где $$$\mathtt{score}$$$ — максимальный балл за этот тест. Иными словами, за каждые $$$\gamma$$$ действий свыше решения жюри в каком-либо из запросов вы теряете один балл за тест.
Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
Подзадача | Баллы | Ограничения | $$$\gamma$$$ | Необходимые подзадачи | Информация о проверке |
0 | $$$2 \times 0$$$ | примеры из условия | $$$100$$$ | полная | |
1 | $$$4 \times 1$$$ | $$$n \le 10$$$ | $$$10$$$ | 0 | первая ошибка |
2 | $$$4 \times 1$$$ | $$$n \le 10$$$ | $$$1$$$ | 0, 1 | первая ошибка |
3 | $$$4 \times 1$$$ | $$$n \le 200$$$, $$$q = 1$$$ | $$$1$$$ | первая ошибка | |
4 | $$$5 \times 2$$$ | $$$q = 1$$$ | $$$1$$$ | 3 | первая ошибка |
5 | $$$5 \times 2$$$ | $$$n \le 200$$$ | $$$1$$$ | 0 – 3 | первая ошибка |
6 | $$$4 \times 1$$$ | $$$a_i = 1$$$ для всех $$$i$$$ | $$$100$$$ | первая ошибка | |
7 | $$$5 \times 2$$$ | $$$a_i = 1$$$ для всех $$$i$$$ | $$$1$$$ | 6 | первая ошибка |
8 | $$$5 \times 3$$$ | $$$a_i \le 2$$$ для всех $$$i$$$; $$$a_i = 2$$$ для не более чем одного $$$i$$$ | $$$50$$$ | 6, 7 | первая ошибка |
9 | $$$5 \times 2$$$ | $$$a_i \le 2$$$ для всех $$$i$$$; $$$a_i = 2$$$ для не более чем одного $$$i$$$ | $$$2$$$ | 6 – 8 | первая ошибка |
10 | $$$9 \times 2$$$ | $$$q \le 4000$$$ | $$$50$$$ | 0 – 9 | первая ошибка |
11 | $$$11 \times 1$$$ | $$$q \le 4000$$$ | $$$2$$$ | 0 – 10 | первая ошибка |
9 4 0 11 2 3 1 2 3 1 2 31 91 64 94 6
6 1 2 3 0 0 0 5 1 2 3 0 0 5 1 2 3 0 0 4 1 2 3 0
12 4 0 11 2 3 4 1 2 3 1 2 3 4 51 122 113 106 7
10 1 2 3 4 0 -1 0 4 5 0 11 2 3 4 1 2 3 1 2 3 4 0 9 3 4 1 2 3 1 2 3 0 3 2 3 0