解题思路
题目要求构造长度为 n 的数组,使得:
- 所有元素之和为 0;
- ∣a1∣,∣a2∣,⋯,∣an∣ 恰好是 1∼n 的一个排列;
- 每个 ai 满足 −n≤ai≤n 且 ai=0。
由于每个绝对值 1∼n 都必须恰好出现一次,本质上就是给 1,2,⋯,n 每个数分配一个正号或负号,使得总和为 0。
题目内容
给定一个整数 n,请你构造一个长度为 n 的数组 {a1,a2,…,an},满足:
- 所有元素之和等于 0;
- {∣a1∣,∣a2∣,…,∣an∣} 恰为 1∼n 的一个排列;
- 对每个i,−n≤ai≤n且 ai=0。
若无解,输出 −1;若有解,可输出任意一组满足条件的数组。
排列:长度为 n 的排列指由 1∼n这n个整数按任意顺序组成的数组,其中每个整数恰好出现一次。
输入描述
每个测试文件均包含多组测试数据。
第一行输入一个整数T(1≤T≤104),代表数据组数。
每组测试数据描述如下:
- 第一行输入一个整数n(1≤n≤2×105),表示数组长度。
除此之外,保证单个测试文件的n之和不超过 2×105。
输出描述
对于每一组测试数据,新起一行:
-
如果无解,输出 −1;
-
否则输出 n 个整数a1,a2,…,an,表示构造出的数组。
如果存在多个合法答案,输出任意一种。
样例1
输入
3
2
3
4
输出
-1
1 2 -3
1 -2 -3 4