牛客6—— Easy Construction （思维+构造）

牛客6—— Easy Construction （思维+构造）

原题链接

题意：

能否构造一个1~n的排列，使得对于任意的 i (1<=i<=n) ，排列都存在一个长度为i的子区间的和%n==k。

思路：

先考虑无解的情况，当i==n时，子区间只有一种情况，元素的和为1+2+……+n，即sum=n*(n+1)/2。如果sum%n!=k的话，说明一定无解。

当n为奇数时，sum%n=0，这时候k=0，可以构造排列：n,1,n-1,2,n-2……

这样除了首项，偶数项+下一个奇数项的和为n,所以就可以当i为奇数时，从首项开始选；当i为偶数时，从第二项开始选。

当n为偶数时，sum%n=n/2，即k=n/2，可以构造排列：n,n/2,1,n-1,2,n-2……

这样从第三项开始，奇数项和下一个偶数项的和为n,所以当i为奇数时，从n/2开始选；当i为偶数时，从n开始选。

代码：

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define I_int ll
typedef pair<int,int> PII;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
const int maxn=1e6+7;
int a[maxn];
int main(){
    int n=read(),k=read();
    if((n*(n+1)/2)%k){
        puts("-1");
        return 0;
    }
    if(n&1){
        a[1]=n;
        for(int i=2,cnt=1;i<=n;i+=2,cnt++){
            a[i]=cnt;a[i+1]=n-cnt;
        }
    }
    else{
        a[1]=n;a[2]=n/2;
        for(int i=3,cnt=1;i<=n;i+=2,cnt++){
            a[i]=cnt;a[i+1]=n-cnt;
        }
    }
    for(int i=1;i<=n;i++) out(a[i]),putchar(' ');
    return 0;
}