CFCF2189C1.XOR Convenience (Easy Version)

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

这是该问题的简单版本。两个版本的区别在于,在这个版本中,约束条件为 2in12 \le i \le n-1。请注意,困难版本的正确解法不一定是简单版本的正确解法。

给定一个自然数 nn。找到一个长度为 nn 的排列 $ ^{*} p$,使得对于每个 ii2in1{\color{red} 2 \le i \le n-1}),都存在一个 jjijn{\color{red}i \le j \le n})满足 pi=pji p_i = p_j \oplus i^{\ \dagger}

可以证明,在问题的约束条件下,至少存在一个满足条件的排列 pp

^{*} 一个长度为 nn 的排列是由 11nnnn 个不同整数按任意顺序组成的数列。例如,[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)。

^{\dagger} \oplus 表示按位异或操作。

输入格式

每个测试数据包含多个测试用例。第一行包含测试用例的数量 tt1t1041 \le t \le 10^4)。每个测试用例的描述如下。

每个测试用例只有一行,包含一个整数 nn3n21053 \leq n \leq 2 \cdot 10^5)——排列的长度。

保证所有测试用例中 nn 的和不超过 21052\cdot 10^5

输出格式

对于每个测试用例,输出 nn 个整数 p1,p2,,pnp_1,p_2,\ldots,p_n ——排列 pp

如果有多种合法方案,你可以输出其中的任何一个。

输入输出样例

  • 输入#1

    2
    3
    6

    输出#1

    2 1 3
    3 6 2 5 1 4

说明/提示

在第一个测试用例中,排列 p=[2,1,3]p = [2,1,3] 是合法的,因为 p2=1p_2 = 1p32=1p_3 \oplus 2 = 1

在第二个测试用例中,排列 p=[3,6,2,5,1,4]p = [3,6,2,5,1,4] 是合法的,因为:

  • p2=6=42=p62p_2 = 6 = 4 \oplus 2 = p_6 \oplus 2
  • p3=2=13=p53p_3 = 2 = 1 \oplus 3 = p_5 \oplus 3
  • p4=5=14=p54p_4 = 5 = 1 \oplus 4 = p_5 \oplus 4
  • p5=1=45=p65p_5 = 1 = 4 \oplus 5 = p_6 \oplus 5
首页