萌新刚学OI,最后一个错了,麻烦大佬看看(是多组数据)
查看原帖
萌新刚学OI,最后一个错了,麻烦大佬看看(是多组数据)
363495
我爱杨帆楼主2020/10/17 15:56
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
int read()
{
	char c;
	int f=1,r=0;
	c=getchar();
	while(c!='-'&&(c<'0'||c>'9'))
	c=getchar();
	if(c=='-')
	{
	f=-1;
    c=getchar();
	}
	while(c>='0'&&c<='9')
	{
	r=r*10+c-'0';
    c=getchar();
	}
	return r*f;
}
int a[25000500],ans[1000],cnt,tot;
int b[1000000],vis[25000500];
inline void solve(int x,int n,int m)
{   
	for(re int i=1;i<=m;i++)
	vis[i]=0;
	vis[1]=1,vis[2]=1,vis[x]=1;
	int sum=b[1]+b[2]+b[x];
	if(sum&1)
	{	
	return;
    }
	sum>>=1;
	a[1]=sum-b[x];
	a[2]=sum-b[2];
	a[3]=sum-b[1];
	if(a[1]<=0||a[2]<=0||a[3]<=0)
	{	
	return;
    }
	for(re int i=4;i<=n;i++)
	{
		int j=3;
		while(vis[j]&&j<=m)
		j++;
		vis[j]=1;
        a[i]=b[j]-a[1];
        if(a[i]<a[i-1])
        {	
		return;
	    }
	    sum+=a[i];
        for(re int k=2;k<i;k++)
        {
        	int num=a[k]+a[i];
        	int p=lower_bound(b+j+1,b+1+m,num)-b;
        	if(p>m)
        	{
			return;
		    }
		    while(vis[p]&&p<=m&&b[p]==b[p+1]&&num==b[p])
		    ++p;
        	if(num!=b[p])
        	{
			return;
		    }
        	vis[p]=1;
		}
	}
	if(sum^cnt)
	{	
	return;
    }
    tot++;
	for(re int i=1;i<=n;i++)
	ans[i]=a[i];
}
signed main()
{int n;
 while(cin>>n)
 {
 tot=0;
 int m=n*(n-1)/2;
 for(re int i=1;i<=m;i++)
 {
 b[i]=read();
 cnt+=b[i];
 }
 sort(b+1,b+1+m);
 cnt/=(n-1);
 for(re int i=3;i<=m;i++)
 if(i==3||b[i]!=b[i-1])
 solve(i,n,m);
 if(!tot)
 {
 cout<<"Impossible";
 //return 0;
 }
 else
 {
 for(re int j=1;j<=n;j++)
 printf("%.lld ",ans[j]);
 printf("\n");
 }
 //return 0;
 }
}
2020/10/17 15:56
加载中...