自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:54:03，当前版本为作者最后更新于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();
}