← 返回题目列表

Codeforces · 1641/B

B. 重复解码

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

Olya 有一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。她想将其分成串联重复。由于这种情况很少发生,因此在此之前她想多次(可能为零)执行以下操作:将一对相等的数字插入到任意位置。帮助她!

更正式地说:

- 串联重复是偶数长度 $$$2k$$$ 的序列 $$$x$$$,这样对于每个 $$$1 \le i \le k$$$ 满足条件 $$$x_i = x_{i + k}$$$。
- 如果您可以将数组 $$$a$$$ 拆分为多个部分,每个部分都是数组的子段,则可以将数组 $$$a$$$ 拆分为串联重复,这样每个部分都是串联重复。
- 在一个操作中,您可以选择任意字母 $$$c$$$ 并将 $$$[c, c]$$$ 插入到数组中的任何位置(开头、任意两个整数之间或末尾)。
- 您将执行多项操作并将数组拆分为串联重复,或者确定这是不可能的。请注意,您不必最小化操作次数。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 30\,000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 500$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 初始数组。

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

输出

对于每个测试用例,按以下格式打印答案。

如果无法将数组转换为串联重复序列的串联,请打印单个整数 $$$-1$$$。

否则打印您想要执行的操作数 $$$q$$$ ($$$0 \le q \le 2 \cdot n^2$$$)。然后打印操作说明。

在下面的每一行 $$$q$$$ 中,打印两个整数 $$$p$$$ 和 $$$c$$$ ($$$1 \le c \le 10^9$$$),这意味着在数组的 $$$p$$$ 元素后面插入整数 $$$c$$$ 两次。如果运算前数组的长度为$$$m$$$,则应满足条件$$$0 \le p \le m$$$。

然后你应该打印任何方式将结果数组分割成串联重复。首先,打印单个整数 $$$d$$$,然后打印大小为 $$$d$$$ 的偶数整数的序列 $$$t_1, t_2, \ldots, t_d$$$ ($$$d, t_i \ge 1$$$)。这些数字是从左到右的子段的长度。

请注意,结果数组 $$$a$$$ 的大小为 $$$m = n + 2 \cdot q$$$。以下陈述必须成立:

- $$$m = \sum\limits_{i = 1}^{d}{t_i}$$$。
- 对于所有整数 $$$i$$$ 使得 $$$1 \le i \le d$$$,序列 $$$a_l, a_{l+1}, \ldots, a_r$$$ 是串联重复,其中 $$$l = \sum\limits_{j = 1}^{i - 1}{t_j} + 1$$$, $$$r = l + t_i - 1$$$。

可以证明,如果数组可以变成串联重复的串联,则存在满足所有约束的解。如果有多个答案,您可以打印任何一个。

示例

输入 #1

4
2
5 7
2
5 5
6
1 3 1 2 2 3
6
3 2 1 1 2 3

输出 #1

-1
0
1
2
4
1 3
5 3
5 3
10 3
2
8 6 
5
0 3
8 3
5 3 
6 2 
7 1
4
2 6 6 2

注意

在第一个测试用例中,您无法对数组应用操作以使其能够将其拆分为串联重复。

在第二个测试用例中,数组已经是串联重复 $$$[5, 5] = \underbrace{([5] + [5])}_{t_1 = 2}$$$,因此我们根本无法执行任何操作。

在第三个测试用例中,最初,我们有以下数组: $$$$$$[1, 3, 1, 2, 2, 3].$$$$$$ 第一次插入 $$$p = 1, c = 3$$$ 后: $$$$$$[1, \textbf{3, 3}, 3, 1, 2, 2, 3].$$$$$$ 第二次插入 $$$p = 5, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, \textbf{3, 3}, 2, 2, 3].$$$$$$ 第三次插入 $$$p = 5, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, \textbf{3, 3}, 3, 3, 2, 2, 3].$$$$$$ 第四次插入后 $$$p = 10, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, 3, 3, 3, 3, 2, \textbf{3, 3}, 2, 3].$$$$$$生成的数组可以表示为串联重复的串联: $$$$$$\underbrace{([1, 3, 3, 3] + [1, 3, 3, 3])}_{t_1 = 8} + \underbrace{([3, 2, 3] + [3, 2, 3])}_{t_2 = 6}.$$$$$$

在第四个测试用例中,最初,我们有以下数组: $$$$$$[3, 2, 1, 1, 2, 3].$$$$$$ 第一次插入 $$$p = 0, c = 3$$$ 后: $$$$$$[\textbf{3, 3}, 3, 2, 1, 1, 2, 3].$$$$$$ 第二次插入后 $$$p = 8, c = 3$$$: $$$$$$[3, 3, 3, 2, 1, 1, 2, 3, \textbf{3, 3}].$$$$$$ 第三次插入后 $$$p = 5, c = 3$$$ $$$$$$[3, 3, 3, 2, 1, \textbf{3, 3}, 1, 2, 3, 3, 3].$$$$$$ 第四次插入后 $$$p = 6, c = 2$$$: $$$$$$[3, 3, 3, 2, 1, 3, \textbf{2, 2}, 3, 1, 2, 3, 3, 3].$$$$$$ 之后第五次插入 $$$p = 7, c = 1$$$: $$$$$$[3, 3, 3, 2, 1, 3, 2, \textbf{1, 1}, 2, 3, 1, 2, 3, 3, 3].$$$$$$ 生成的数组可以表示为串联重复的串联: $$$$$$\underbrace{([3] + [3])}_{t_1 = 2} + \underbrace{([3, 2, 1] + [3, 2, 1])}_{t_2 = 6} + \underbrace{([1, 2, 3] + [1, 2, 3])}_{t_3 = 6} + \underbrace{([3] + [3])}_{t_4 = 2}.$$$$$$