← 返回题目列表

Codeforces · 1042/C

C. 数组产品

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您可以使用它执行以下操作:

1. 选择一些位置 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n, i \ne j$$$),将 $$$a_i \cdot a_j$$$ 的值写入第 $$$j$$$ 个单元格,并删除第 $$$i$$$ 个单元格中的数字;
2. 选择某个位置 $$$i$$$ 并从第 $$$i$$$ 个单元格中删除该数字(此操作可以在任何时间点执行不超过一次,不一定在开始时执行)。

每次操作后元素数量减一。然而,头寸的索引保持不变。删除的号码无法在后续操作中使用。

您的任务是对数组执行 $$$n - 1$$$ 操作,以使数组中保留的唯一数字尽可能大。该数字可能相当大,因此您不需要打印它,而是需要打印导致该最大数字的任何操作序列。阅读输出格式以了解您到底需要打印什么。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组中的元素数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组的元素。

输出

打印 $$$n - 1$$$ 行。第 $$$k$$$ 行应包含两个可能的操作之一。

第一种类型的操作应如下所示:$$$1~ i_k~ j_k$$$,其中$$$1$$$是操作类型,$$$i_k$$$和$$$j_k$$$是所选元素的位置。

第二种类型的操作应如下所示:$$$2~ i_k$$$,其中$$$2$$$是操作类型,$$$i_k$$$是所选元素的位置。请注意,这样的操作不应超过一个。

如果有多个可能的操作序列导致最大数量 - 打印其中任何一个。

示例

输入 #1

5
5 -2 0 1 -3

输出 #1

2 3
1 1 2
1 2 4
1 4 5

输入 #2

5
5 2 0 4 0

输出 #2

1 3 5
2 5
1 1 2
1 2 4

输入 #3

2
2 -1

输出 #3

2 2

输入#4

4
0 -10 0 0

输出#4

1 1 2
1 2 3
1 3 4

输入 #5

4
0 0 0 0

输出 #5

1 1 2
1 2 3
1 3 4

注意

令 X 为数组中被删除的数字。让我们看一下所有的例子:

例如,第一个示例具有以下数组转换序列: $$$[5, -2, 0, 1, -3] \to [5, -2, X, 1, -3] \to [X, -10, X, 1, -3] \to$$$ $$$[X, X, X, -10, -3] \to [X, X, X, X, 30]$$$。因此,最大答案是 $$$30$$$。请注意,导致答案 $$$30$$$ 的其他序列也是正确的。

例如,第二个示例具有以下数组转换序列: $$$[5, 2, 0, 4, 0] \to [5, 2, X, 4, 0] \to [5, 2, X, 4, X] \to [X, 10, X, 4, X] \to$$$ $$$[X, X, X, 40, X]$$$。以下答案也是允许的:

那么数组的转换顺序将如下所示: $$$[5, 2, 0, 4, 0] \to [5, 2, 0, 4, X] \to [5, 8, 0, X, X] \to [40, X, 0, X, X] \to$$$ $$$[40, X, X, X, X]$$$。

第三个示例可以具有以下数组转换序列:$$$[2, -1] \to [2, X]$$$。

第四个示例可以具有以下数组转换序列:$$$[0, -10, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$$$。

第五个示例可以具有以下数组转换序列:$$$[0, 0, 0, 0] \to [X, 0, 0, 0] \to [X, X, 0, 0] \to [X, X, X, 0]$$$。