Codeforces Round 829 (Div. 1) |
---|
Закончено |
Это сложная версия задачи. Разница между версиями заключается в том, что в этой версии массив содержит нули. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Вам дан массив $$$[a_1, a_2, \ldots a_n]$$$, состоящий из чисел $$$-1$$$, $$$0$$$ и $$$1$$$. Требуется предъявить разбиение этого массива на несколько отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$, обладающее следующим свойством:
Обратите внимание, каждое $$$s_i$$$ не обязано равняться 0, условие стоит только на сумму $$$s_i$$$ по всем отрезкам разбиения.
Набор отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$ называется разбиением массива $$$a$$$ длины $$$n$$$, если $$$1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$$$, причем для всех $$$i = 1, 2, \ldots k-1$$$ выполняется $$$r_i + 1 = l_{i+1}$$$. Иными словами, каждый элемент массива должен принадлежать ровно одному отрезку.
Требуется предъявить разбиение массива, обладающее описанными свойствами, или сказать, что такого разбиения не существует.
Обратите внимание, минимизировать количество отрезков в разбиении не требуется.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следуют описания наборов:
Первая строка каждого описания содержит единственное целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$) — длину массива $$$a$$$.
Вторая строка каждого описания содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i$$$ равно $$$-1$$$, $$$0$$$ или $$$1$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.
Для каждого набора входных данных выведите целое число $$$k$$$ — количество отрезков в получившемся разбиении. Если требуемого разбиения не существует, выведите $$$-1$$$.
Далее, если разбиение существует, то в $$$i$$$-й из следующих $$$k$$$ строк выведите два целых числа $$$l_i$$$ и $$$r_i$$$ — границы $$$i$$$-го отрезка. При этом должны выполняться условия:
Если существует несколько корректных разбиений массива на отрезки, разрешается вывести любое из них.
540 0 0 07-1 1 0 1 0 1 050 -1 1 0 131 0 111
4 1 1 2 2 3 3 4 4 4 1 1 2 2 3 5 6 7 -1 2 1 1 2 3 -1
В первом наборе входных данных массив можно просто разбить на $$$4$$$ отрезка по одному элементу, равному $$$0$$$. Тогда общая сумма будет равна $$$0 + 0 + 0 + 0 = 0$$$.
Во втором наборе входных данных массив разбивается на $$$4$$$ отрезка. На первом из них знакопеременная сумма будет равна $$$-1$$$, на втором $$$1$$$, на третьем $$$0 - 1 + 0 = -1$$$, на четвёртом $$$1 - 0 = 1$$$. Получаем общую сумму: $$$-1 + 1 -1 + 1 = 0$$$.
В третьем наборе входных данных можно показать, что требуемого разбиения не существует.
Название |
---|