← 返回题目列表

Codeforces · 1753/A2

A2. 使非零和(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。不同之处在于,在此版本中,数组包含零。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

给定一个数组 $$$[a_1, a_2, \ldots a_n]$$$,由整数 $$$-1$$$、$$$0$$$ 和 $$$1$$$ 组成。您必须将此数组的分区构建为段集 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$ ,具有以下属性:

- 将第$$$i$$$段的所有元素的交替和表示为$$$s_i$$$:$$$s_i$$$ = $$$a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}$$$。例如,数组 $$$[1, 0, -1, 1, 1]$$$ 中段 $$$[2, 4]$$$ 的元素交替和等于 $$$0 - (-1) + 1 = 2$$$。
- 所有分区段的 $$$s_i$$$ 总和应等于 0。

请注意,每个 $$$s_i$$$ 不必等于零,此属性约为分区所有段上 $$$s_i$$$ 的总和。

段集合 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$$$ 称为长度为 $$$n$$$ 的数组 $$$a$$$ 的分区,如果 $$$1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$$$ 和 $$$r_i + 1 = l_{i+1}$$$ 对于所有 $$$i = 1, 2, \ldots k-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$$$。

如果分区存在,则在以下 $$$k$$$ 行的第 $$$i$$$ 行中打印两个整数 $$$l_i$$$ 和 $$$r_i$$$ - 第 $$$i$$$ 段的描述。应满足以下条件:

- $$$l_i \le r_i$$$ 对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$。
- $$$l_{i + 1} = r_i + 1$$$ 对于从 $$$1$$$ 到 $$$(k - 1)$$$ 的每个 $$$i$$$。
- $$$l_1 = 1,r_k = n$$$。

如果数组有多个正确的分区,则打印其中的任何一个。

示例

输入 #1

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

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$$$。

在第三个测试用例中可以证明所需的分区不存在。