Submission #33635759

---

Source Code Expand

// Problem: D - Non Arithmetic Progression Set
// Contest: AtCoder - AtCoder Regular Contest 145
// URL: https://atcoder.jp/contests/arc145/tasks/arc145_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms

#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
const uint Lim=1e7;
uint Prime[2000005],tp;
bol Gone[Lim+1];
int Used[2000005];
uint Id[Lim+1];
uint n;llt m;
uint cnt=0;llt sum=0;
voi Output(llt v)
{
	printf("%lld ",v);
	cnt++;sum+=v;
}
voi print()
{
	for(uint i=0;i<tp;i++)if(Used[i])Output((llt)Used[i]*Prime[i]);
	puts("");
	if(sum!=m||cnt!=n)puts("\nWA"),exit(1);
	exit(0);
}
voi dfs(uint n,llt v,uint tp)
{
	if(!n){
		if(!v)print();
		return;
	}
	if(!v)
	{
		if(n==1)Output(0),n=0;
		if(n&1){Used[0]=Used[1]=1,Used[2]=-1,n-=3;}
		for(uint i=::tp-1;n;i--)if(!Used[i])Output(Prime[i]),Output(-(int)Prime[i]),n-=2;
		print();
	}
	if(abs(v)<=Lim&&!Gone[abs(v)]&&!Used[Id[abs(v)]])
	{
		Used[Id[abs(v)]]=v>0?1:-1;
		dfs(n-1,0,0);
	}
	if(n==1)return;
	for(uint i=tp-1;i>2;i--)if(!Used[i])
	{
		if(v>0)Used[i]=1,dfs(n-1,v-Prime[i],i);
		else Used[i]=-1,dfs(n-1,v+Prime[i],i);
		Used[i]=0;
	}
	return;
}
int main()
{
	Gone[0]=Gone[1]=true;
    for(uint i=2;i<=Lim;i++)if(!Gone[i]){Prime[Id[i]=tp++]=i;for(uint j=i<<1;j<=Lim;j+=i)Gone[j]=true;}
    // printf("%u\n",tp);
    scanf("%u%lld",&n,&m);
    if(n==1)printf("%lld\n",m);
    else if(n==2)printf("0 %lld\n",m);
    else dfs(n,m,tp-1),exit(1);
    return 0;
}

Submission Info

Judge Result