← 返回题目列表

Codeforces · 1353/D

D. 构造数组

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

给定一个数组 $$$a$$$,长度为 $$$n$$$,由零组成。 You perform $$$n$$$ actions with this array: during the $$$i$$$-th action, the following sequence of operations appears:

1. 选择长度最大且仅由零组成的子数组(连续子段),在所有此类段中选择最左边的一个;
2. 令该段为$$$[l; r]$$$。如果 $$$r-l+1$$$ 是奇数(不能被 $$$2$$$ 整除),则赋值(设置)$$$a[\frac{l+r}{2}] := i$$$ (其中 $$$i$$$ 是当前操作的编号),否则(如果 $$$r-l+1$$$ 是偶数)赋值(设置)$$$a[\frac{l+r-1}{2}] :=我$$$。

考虑长度为 $$$5$$$ 的数组 $$$a$$$ (最初 $$$a=[0, 0, 0, 0, 0]$$$)。那么它的变化如下:

1. Firstly, we choose the segment $$$[1; 5]$$$ 并赋值 $$$a[3] := 1$$$,因此 $$$a$$$ 变为 $$$[0, 0, 1, 0, 0]$$$;
2.然后我们选择段$$$[1; 2]$$$ 并赋值 $$$a[1] := 2$$$,因此 $$$a$$$ 变为 $$$[2, 0, 1, 0, 0]$$$;
3.然后我们选择段$$$[4; 5]$$$ 并赋值 $$$a[4] := 3$$$,因此 $$$a$$$ 变为 $$$[2, 0, 1, 3, 0]$$$;
4.然后我们选择段$$$[2; 2]$$$ 并赋值 $$$a[2] := 4$$$,因此 $$$a$$$ 变为 $$$[2, 4, 1, 3, 0]$$$;
5.最后我们选择段$$$[5; 5]$$$ 并赋值 $$$a[5] := 5$$$,因此 $$$a$$$ 变为 $$$[2, 4, 1, 3, 5]$$$。

你的任务是在执行所有 $$$n$$$ 操作后找到长度为 $$$n$$$ 的数组 $$$a$$$。请注意,答案存在且唯一。

您必须回答 $$$t$$$ 独立测试用例。

输入

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

测试用例的唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案 — 在执行问题陈述中描述的 $$$n$$$ 操作后,长度为 $$$n$$$ 的数组 $$$a$$$。请注意,答案存在且唯一。

示例

输入 #1

6
1
2
3
4
5
6

输出 #1

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