C. The 67th Permutation Problem

    传统题 2000ms 256MiB

The 67th Permutation Problem

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

到达学校后,Macaque 被他的朋友 AG-88301 相当粗暴地打招呼了。后者整晚都在喋喋不休地向一位毫无防备的陌生人讲述他关于 Collatz 猜想证明的开创性工作以及他第 6767 次单恋,因此翘掉了作业。于是,像往常一样,AG-88301 以越来越少的感激或赞赏,让 Macaque 替他做作业。此时,Macaque 已经受够了,于是转向他的手下(你们!)来解决 AG-88301 的作业任务。

给定一个整数 nn。你需要构造一个长度为 3n3n 的排列∗^{\text{∗}},使得将该排列划分为 nn 个每段 33 个元素的连续块后,这些块的中位数†^{\text{†}}之和最大化。

更形式化地,你需要构造一个长度为 3n3n 的排列 pp,使得 $\sum_{i=0}^{n-1}\operatorname{median}(a_{3i+1},a_{3i+2},a_{3i+3})$ 最大化。如果有多个可行的 pp,输出任意一个即可。

∗^{\text{∗}}长度为 nn 的排列是由 11 到 nn 的 nn 个不同整数以任意顺序组成的数组。例如,[2,3,1,5,4][2,3,1,5,4] 是一个排列,但 [1,2,2][1,2,2] 不是排列(22 在数组中出现了两次),[1,3,4][1,3,4] 也不是排列(n=3n=3 但数组中有 44)。

†^{\text{†}}包含 33 个元素的数组 bb 的中位数是将 bb 按非降序排序后第 22 个元素。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1041 \le t \le 10^4)。接下来是每个测试用例的描述。

每个测试用例的唯一一行包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5)。

保证所有测试用例中 3n3n 的总和不超过 3⋅1053 \cdot 10^5。

输出格式

对于每个测试用例,输出一个排列 pp,使得连续块的中位数之和最大化。如果有多个可行的 pp,输出任意一个即可。

样例

3
2
1
3
1 3 4 2 5 6 
3 1 2
5 2 4 8 3 9 7 1 6

说明

在第一个测试用例中,[1,3,4,2,5,6][1,3,4,2,5,6] 是一个可行的答案,因为 $\operatorname{median}(1,3,4) + \operatorname{median}(2,5,6) = 3+5 = 8$,并且可以证明 88 是中位数之和的最大可能值。

在第二个测试用例中,[3,1,2][3,1,2] 是一个可行的答案,因为当 n=1n=1 时唯一可达的中位数之和为 22。

Codeforces Round 1090 (Div. 4)

未参加
状态
已结束
规则
XCPC
题目
7
开始于
2026-11-11 15:00
结束于
2026-11-11 17:30
持续时间
2.5 小时
主持人
参赛人数
14