← 返回题目列表

Codeforces · 1474/E

E. 这是什么?

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

月球车终于到达X行星。着陆后,他遇到了一个障碍,其中包含长度为$$$n$$$的排列$$$p$$$。科学家发现,为了克服障碍,机器人应该对 $$$p$$$ 进行身份排列(对所有 $$$i$$$ 进行 $$$p_i = i$$$)。

不幸的是,科学家无法控制机器人。因此,使 $$$p$$$ 成为恒等排列的唯一方法是对 $$$p$$$ 多次应用以下操作:

- 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$i \neq j$$$),使得 $$$p_j = i$$$ 并交换 $$$p_i$$$ 和 $$$p_j$$$ 的值。机器人需要 $$$(j - i)^2$$$ 秒来完成此操作。

科学家要求您找出机器人完成 $$$p$$$ 身份排列(即最坏情况)所需的最大可能时间,以便他们可以决定是应该建造一个新的月球车还是只是休息和等待。如果没有证据,他们不会相信你,所以你应该构建一个 $$$p$$$ 和机器人操作的示例,以最大化答案。

为了更好地理解该语句,请阅读示例描述。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

接下来的 $$$t$$$ 行包含单个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) – $$$p$$$ 的长度。

请注意,$$$p$$$ 不是给你的。您应该找到长度为 $$$n$$$ 的所有排列的最大可能时间。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于第一行中的每个测试用例,打印机器人在最坏情况下将花费多少秒。

在下一行中,打印用于构造答案的 $$$p$$$ 的初始值。

在下一行中,打印机器人在示例中执行的操作数 $$$m \leq n$$$。

在接下来的 $$$m$$$ 行中,打印两个整数 $$$i$$$ 和 $$$j$$$ - 机器人在此操作中将交换的位置索引。请注意,$$$p_j = i$$$ 必须成立(在操作时)。

示例

输入 #1

3
2
3
3

输出 #1

1
2 1
1
2 1
5
2 3 1
2
1 3
3 2
5
2 3 1
2
1 3
2 3

注意

对于 $$$n = 2$$$,$$$p$$$ 可以是 $$$[1, 2]$$$ 或 $$$[2, 1]$$$。在第一种情况下,$$$p$$$ 已经是恒等,否则机器人将在第二次 $$$1$$$ 中使其成为恒等排列,而不管第一次操作中选择 $$$i$$$ 和 $$$j$$$ 。

对于 $$$n = 3$$$,$$$p$$$ 可以等于 $$$[2, 3, 1]$$$。

- 如果机器人在第一次操作时选择 $$$i = 3, j = 2$$$,$$$p$$$ 将在一秒内变成 $$$[2, 1, 3]$$$。现在机器人只能选择 $$$i = 1, j = 2$$$ 或 $$$i = 2, j = 1$$$。在这两种情况下,$$$p$$$ 将在一秒后成为身份(总共 $$$2$$$ 秒)。
- 如果机器人在第一次操作时选择 $$$i = 1, j = 3$$$,$$$p$$$ 将在四秒内变成 $$$[1, 3, 2]$$$。无论第二次操作中$$$i$$$ 和$$$j$$$ 的选择如何,$$$p$$$ 将在五秒内变为恒等。

我们可以证明,对于长度 $$$3$$$ 的排列,机器人总是会在不超过 $$$5$$$ 秒内完成所有操作。