CF1352G Special Permutation

CF1352G Special Permutation

一道巧妙的构造题。
首先对于(n<4)，经过手算可以发现是没有这样的一组数据的。那么也就是找找(n geq 4)的情况。

注意到这道题构造的特点是(2leq|p_i-p_{i+1}|leq 4)。那么(2)和(4)是什么呢？构造题按照套路奇偶性一般都是要考虑的。那么(2)其实就是相邻两个奇(偶)数的差，(4)也就是中间隔着一个的两个奇(偶)数的差。

举个例子，当(n=9)时，奇数有(1,3,5,7,9)，偶数有(2,4,6,8)。不妨考虑先把奇数从小到大排好，这样每两个数的差都是(2)，满足条件。如果我们之后再将偶数从大到小排序，构成(1,3,5,7,9,8,6,4,2)，中间两个数的差就是(1)，显然不满足。这时如果我们将(6,8)交换位置，原数列变成了(1,3,5,7,9,6,8,4,2)就可以了。

当(n=10)时，奇数有(1,3,5,7,9)，偶数有(2,4,6,8,10)。这时先排奇数不行了，我们考虑先排偶数再排奇数。(1,3,5,7,9,10,8,6,4,2)。这样的话按照之前的策略交换(8,10)也是可以满足的，交换以后的数列变成(1,3,5,7,9,8,10,6,4,2)

于是总的策略就是先分奇偶，再按照上面的方法进行构造。

代码：

#include<bits/stdc++.h>
using namespace std;
int t;
void work1(int x)
{
	for(int i = 2; i <= x; i += 2) printf("%d ", i);
	printf("%d %d ", x - 3, x - 1);
	for(int i = x - 5; i >= 1; i -= 2) printf("%d ", i);
	printf("
");
}
void work2(int x)
{
	for(int i = 1; i <= x; i += 2) printf("%d ", i);
	printf("%d %d ", x - 3, x - 1);
	for(int i = x - 5; i >= 2; i -= 2) printf("%d ", i);
	printf("
");
}
int main()
{
	scanf("%d", &t);
	while(t --)
	{
		int n;
		scanf("%d", &n);
		if(n < 4) printf("-1
");
		else
		{
			if(n % 2 == 0) work1(n);
			if(n % 2 == 1) work2(n);
		}
	}
}