Codeforces Round 829 (Div. 1) |
---|
Закончено |
Это простая версия задачи. Разница между версиями заключается в том, что в этой версии массив не содержит нулей. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Вам дан массив $$$[a_1, a_2, \ldots a_n]$$$, состоящий из чисел $$$-1$$$ и $$$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$$$ или $$$1$$$) — элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.
Для каждого набора входных данных выведите целое число $$$k$$$ — количество отрезков в получившемся разбиении. Если требуемого разбиения не существует, выведите $$$-1$$$.
Далее, если разбиение существует, то в $$$i$$$-й из следующих $$$k$$$ строк выведите два целых числа $$$l_i$$$ и $$$r_i$$$ — границы $$$i$$$-го отрезка. При этом должны выполняться условия:
Если существует несколько корректных разбиений массива на отрезки, разрешается вывести любое из них.
441 1 1 16-1 1 1 1 1 131 -1 111
1 1 4 2 1 3 4 6 -1 -1
В первом наборе входных данных массив можно разбить на один отрезок длины $$$4$$$. Сумма на этом отрезке будет равна $$$1 - 1 + 1 - 1 = 0$$$.
Во втором наборе входных данных массив можно разбить на два отрезка длины $$$3$$$. В первом из них знакопеременная сумма будет равна $$$-1 -1 + 1 = -1$$$, а во втором: $$$1 - 1 + 1 = 1$$$. Получаем общую сумму: $$$-1 + 1 = 0$$$.
В третьем и четвертом наборах входных данных можно показать, что требуемого разбиения не существует.
Название |
---|