思路
首先，可以通过暴力看出来只有很少的数满足 $\frac{n \times (n + 1)}{2}$ 是完全平方数，所以我们可以先设定一个原始的排序方式，就是从 $1$ 到 $n$。
我们先判断，如果 $\frac{n \times (n + 1)}{2}$ 是完全平方数，那么直接判断为无解，因为没有任何方法的排序，能让这个排序的总和是完全平方数。
如果不是无解，那么我们需要从 $1$ 开始往后便利，来判断如果从 $1$ 加到现在是不是完全平方数。
如果发现加到 $i$ 是完全平方数，那么我们需要一个调换的方法，把这个数换掉，但是改动的要尽量少，不然我们后面的有很多要处理的。
这个方法就是调换 $i$ 和 $i + 1$，因为假设 $\frac{i \times (i + 1)}{2}$ 是完全平方数 $x ^2$，那么 $x ^ 2 + 1$ 就绝对不是完全平方数，因为下一个离 $x ^ 2$ 最近且大于 $x ^ 2$ 的完全平方数就是 $(x + 1) ^ 2$。而 $(x + 1) ^ 2 – x ^ 2 = (x+1-x) * (x+1+x) = 2 \times x + 1$，也就是只有当 $x = 0$ 的时候调换后还是完全平方数，而由于 $i$ 从 $1$ 开始的，所以 $x$ 不可能等于 $0$，调换后也就不可能是完全平方数了。
这个方法就是还有一个问题，就是如果 $1$ 加到 $i + 1$ 还是完全平方数的话也不行。假设 $\frac{n \times (n + 1)}{2} = x ^ 2$ 且 $\frac{(n + 1) \times (n + 2)}{2} = y ^ 2$，那么 $(y – x) \times (y + x) = n + 1$。又因为 $n = \sqrt{ x^2 + x ^ 2 + n} < 2x$，但是 $y \geq x + 1$，所以 $(y – x) \times (y + x) > n + 1$，所以不存在任何一个 $y$ 满足条件。所以如果 $1$ 加到 $i$ 是完全平方数的情况下，$1$ 加到 $i + 1$ 不会是完全平方数。
既然证明了，我们就可以按照以下步骤完成程序：
- 让 $p$ 数组初始的时候设为从 $1$ 到 $n$
- 从 $1$ 开始遍历，如果遇到加到现在的和是完全平方数，那么就交换 $i$ 和 $i + 1$。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int _T; cin >> _T;
while (_T --) {
long long x; cin >> x;
long long cnt = x * (x + 1) / 2;
if (x < 2 || (int)(ceil(sqrt(cnt)) * ceil(sqrt(cnt))) == cnt) cout << "-1\n";
else {
// cout << (int(ceil(sqrt(cnt)) * ceil(sqrt(cnt))) == cnt) << "\n";
vector <int> v;
long long sum = 2;
cout << "2 ";
for (int i = 1; i <= x; i ++) {
if (i == 2) continue;
sum += i;
if ((int)(sqrt(sum)) * (int)(sqrt(sum)) == sum) {
sum += i + 1;
cout << i + 1 << " " << i << " ";i ++;
} else cout << i << " ";
}
cout << "\n";}
}
}提交记录：https://codeforces.com/problemset/submission/2071/309907754