CFCF2189C1.XOR Convenience (Easy Version)
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
这是该问题的简单版本。两个版本的区别在于,在这个版本中,约束条件为 2≤i≤n−1。请注意,困难版本的正确解法不一定是简单版本的正确解法。
给定一个自然数 n。找到一个长度为 n 的排列 $ ^{*} p$,使得对于每个 i(2≤i≤n−1),都存在一个 j(i≤j≤n)满足 pi=pj⊕i †。
可以证明,在问题的约束条件下,至少存在一个满足条件的排列 p。
∗ 一个长度为 n 的排列是由 1 到 n 的 n 个不同整数按任意顺序组成的数列。例如,[2,3,1,5,4] 是一个排列,但 [1,2,2] 不是排列(2 在数列中出现两次),[1,3,4] 也不是排列(n=3 但数列中有 4)。
† ⊕ 表示按位异或操作。
输入格式
每个测试数据包含多个测试用例。第一行包含测试用例的数量 t (1≤t≤104)。每个测试用例的描述如下。
每个测试用例只有一行,包含一个整数 n (3≤n≤2⋅105)——排列的长度。
保证所有测试用例中 n 的和不超过 2⋅105 。
输出格式
对于每个测试用例,输出 n 个整数 p1,p2,…,pn ——排列 p 。
如果有多种合法方案,你可以输出其中的任何一个。
输入输出样例
输入#1
2 3 6
输出#1
2 1 3 3 6 2 5 1 4
说明/提示
在第一个测试用例中,排列 p=[2,1,3] 是合法的,因为 p2=1 和 p3⊕2=1 。
在第二个测试用例中,排列 p=[3,6,2,5,1,4] 是合法的,因为:
- p2=6=4⊕2=p6⊕2
- p3=2=1⊕3=p5⊕3
- p4=5=1⊕4=p5⊕4
- p5=1=4⊕5=p6⊕5