← 返回题目列表

Codeforces · 1753/A1

A1. 使非零和(简单版)

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

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

给定一个数组 $$$[a_1, a_2, \ldots a_n]$$$,由整数 $$$-1$$$ 和 $$$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$$$ 或 $$$1$$$)——给定数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,如果所需分区不存在,则打印 $$$-1$$$。否则,打印一个整数 $$$k$$$ — 分区中的段数。

然后在接下来的 $$$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

4
4
1 1 1 1
6
-1 1 1 1 1 1
3
1 -1 1
1
1

输出 #1

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

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