自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:17:20，当前版本为作者最后更新于2025-08-07 18:46:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单构造题。

首先偶数个排列显然可以 S 形构造。

奇数个排列时，如果长度是偶数，每一个数的下标和显然不是整数，于是无解。

于是只剩长度奇数的情况。

先考虑三个排列的构造。

不妨将第一个升序排序。

注意到每个下标的加和为 $3\times\frac{(1+m)}{2}$，然后第一个和第二个排列造成的贡献要刚好落满 $[3\times\frac{(1+m)}{2}-m,3\times\frac{(1+m)}{2}-1]$。

容易想到这么一个构造，在前两个排列搞出 $(1,m),(2,m-2),(3,m-4),\dots,(k,m-2k),(k+1,2m-2(k+1)),\dots,(k+d,2m-2k-2d)$ 这样的对，然后根据这个填第三个排列。

由于 $m$ 是奇数，刚好满足限制。

去掉这三个就变成偶数局面，解法一样同上。

于是做完了。

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n,m;
    cin>>n>>m;
    if(n==1){
        if(m!=1)puts("-1");
        else puts("1");
        return;
    }
    if(n&1){
        if(m&1){
            map<int,int>mp;
            for(int i=1;i<=m;i++)cout<<i<<" ";cout<<'\n';
            for(int i=1,j=m;i<=m;i++,j=(j-2+m)%m)mp[j]=i;
            for(int i=1;i<=m;i++)cout<<mp[i]<<" ";cout<<'\n';
            for(int i=1,j=m;i<=m;i++,j=(j-2+m)%m)mp[((1+m)/2)*3-j-i]=i;
            for(int i=1;i<=m;i++)cout<<mp[i]<<" ";cout<<'\n';
        }else{
            puts("-1");
            return;
        }
        n-=3;
    }
    while(n){
        for(int i=1;i<=m;i++)cout<<i<<' ';cout<<'\n';
        for(int i=m;i;i--)cout<<i<<' ';cout<<'\n';
        n-=2;
    }
}
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(),cout.tie();
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}