P10033 「Cfz Round 3」Sum of Permutation 题解

_•́へ•́╬_ · 2023-12-31 20:58:07 · 题解

思路

我想全填 1。

cfz 说，不行，原排列有个 1，撞车了。

暴力枚举原排列那个 1 的位置填啥，其他地方全填 1。

cfz 说，不行，2 1 3。

那就暴力枚举原排列那个 n 的位置填啥，其他地方全填 n。

cfz 哭了，他卡不掉。

确实不存在以上两种方法都失败的情况。

code

检验合法性的复杂度是 \mathcal O(n\log n) 的。比标算稍劣。无所谓，cfz 本来想卡这个的来着，但是加个快读快写随便冲。

#include<stdio.h>
#include<algorithm>
#define N 1000009
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
inline void pc(char x)
{
    static char buf[99999],*r=buf;
    (!x||(*r++=x,r==buf+99999))&&(fwrite(buf,1,r-buf,stdout),r=buf);
}
inline void pr(int x){if(x>9)pr(x/10);pc(x%10+'0');}
int t,n,m,a[N],b[N];long long c[N];
struct __readt__
{
    inline __readt__(){read(t);}
    inline~__readt__(){pc(0);}
}_readt___;
inline bool jg()
{
    c[0]=0;for(int i=1;i<=n;++i)c[i]=c[i-1]+a[i]-b[i];
    sort(c,c+n+1);
    for(int i=0;i<n;++i)if(c[i]==c[i+1])return 0;
    return 1;
}
main()
{
    read(n);for(int i=1;i<=n;read(a[i++]));
    for(int i=1;i<=n;b[i++]=1)if(a[i]==1)m=i;
    for(++b[m];b[m]<=n;++b[m])if(jg())
    {
        for(int i=1;i<=n;pr(b[i++]),pc(' '));
        goto nxt;
    }
    for(int i=1;i<=n;b[i++]=n)if(a[i]==n)m=i;
    for(--b[m];b[m];--b[m])if(jg())
    {
        for(int i=1;i<=n;pr(b[i++]),pc(' '));
        goto nxt;
    }
    pc('-');pc('1');pc('\n');
    nxt:if(--t)main();
}