Задача №115162. Нулевая сумма
Вам дан массив \([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\) знакопеременную сумму элементов в \(i\)-м отрезке, то есть \(s_i\) = \(a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}\). Например знакопеременная сумма на отрезке \([2, 4]\) в массиве \([1, 0, -1, 1, 1]\) равна \(0 - (-1) + 1 = 2\).
- Сумма значений \(s_i\) по всем отрезкам из разбиения должна быть равна нулю.
Обратите внимание, каждое \(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\)-го отрезка. При этом должны выполняться условия:
- \(l_i \le r_i\) для всех \(i\) от \(1\) до \(k\).
- \(l_{i + 1} = r_i + 1\) для всех \(i\) от \(1\) до \((k - 1)\).
- \(l_1 = 1, r_k = n\).
Если существует несколько корректных разбиений массива на отрезки, разрешается вывести любое из них.
В первом наборе входных данных массив можно просто разбить на \(4\) отрезка по одному элементу, равному \(0\). Тогда общая сумма будет равна \(0 + 0 + 0 + 0 = 0\).
Во втором наборе входных данных массив разбивается на \(4\) отрезка. На первом из них знакопеременная сумма будет равна \(-1\), на втором \(1\), на третьем \(0 - 1 + 0 = -1\), на четвёртом \(1 - 0 = 1\). Получаем общую сумму: \(-1 + 1 -1 + 1 = 0\).
В третьем наборе входных данных можно показать, что требуемого разбиения не существует.
5 4 0 0 0 0 7 -1 1 0 1 0 1 0 5 0 -1 1 0 1 3 1 0 1 1 1
1 1 4 5 1 1 2 2 3 5 6 6 7 7 -1 2 1 1 2 3 -1