Submission #73247

#	Time	Username	Problem	Language	Result	Execution time	Memory
73247		zscoder	Toys (CEOI18_toy)	C++17	100 / 100	971 ms	40864 KiB

toy

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<ii> pf;
vector<int> primes;
bool isprime[111111];

void init(int n)
{
	for(int i=2;i<=n;i++)
	{
		isprime[i]=1;
	}
	for(int i=2;i<=n;i++)
	{
		if(isprime[i])
		{
			primes.pb(i);
			for(int j=2*i;j<=n;j+=i)
			{
				isprime[j]=0;
			}
		}
	}
}

int power[32][32];
set<int> dp[32][32][32];
int P[6][111];
set<multiset<int> > partitions[(1<<10)+1];
set<int> ans;
set<int> D[11][32][32][32];

void solve(multiset<int> cur, int a, int b, int c)
{
	vector<int> vec;
	for(int x:cur) vec.pb(x);
	for(int z=0;z<=cur.size();z++)
	{
		for(int i=0;i<=a;i++)
		{
			for(int j=0;j<=b;j++)
			{
				for(int k=0;k<=c;k++)
				{
					D[z][i][j][k].clear();
				}
			}
		}
	}
	D[0][a][b][c].insert(0);
	for(int z=0;z<vec.size();z++)
	{
		for(int i=0;i<=a;i++)
		{
			for(int j=0;j<=b;j++)
			{
				for(int k=0;k<=c;k++)
				{
					if(!D[z][i][j][k].empty())
					{
						for(int l=0;l<=i;l++)
						{
							for(int m=0;m<=j;m++)
							{
								for(int x=0;x<=k;x++)
								{
									for(int s:D[z][i][j][k])
									{
										D[z+1][i-l][j-m][k-x].insert(s+vec[z]*P[2][l]*P[3][m]*P[5][x]-1);
									}
								}
							}
						}
					}
				}
			}
		}
	}
	for(int i=0;i<=a;i++)
	{
		for(int j=0;j<=b;j++)
		{
			for(int k=0;k<=c;k++)
			{
				for(int s:D[int(vec.size())][i][j][k])
				{
					for(int t:dp[a-i][b-j][c-k])
					{
						ans.insert(s+t);
					}
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	init(100000);
	for(int p:primes)
	{
		int cnt=0;
		while(n%p==0)
		{
			cnt++; n/=p;
		}
		if(cnt>0) pf.pb(mp(p,cnt));
	}
	if(n>1) pf.pb(mp(n,1));
	for(int i=1;i<=5;i++)
	{
		P[i][0]=1;
		for(int j=1;j<=32;j++)
		{
			P[i][j]=P[i][j-1]*i;
		}
	}
	for(int i=0;i<pf.size();i++)
	{
		power[i][0]=1;
		for(int j=1;j<=pf[i].se;j++)
		{
			power[i][j]=power[i][j-1]*pf[i].fi;
		}
	}
	int a=0; int b=0; int c=0;
	for(int i=0;i<pf.size();i++)
	{
		if(pf[i].fi==2) a+=pf[i].se;
		if(pf[i].fi==3) b+=pf[i].se;
		if(pf[i].fi==5) c+=pf[i].se;
	}
	dp[a][b][c].insert(0);
	for(int i=a;i>=0;i--) //lazy to optimize lul, try if needed
	{
		for(int j=b;j>=0;j--)
		{
			for(int k=c;k>=0;k--)
			{
				for(int l=0;l<=i;l++)
				{
					for(int m=0;m<=j;m++)
					{
						for(int x=0;x<=k;x++)
						{
							if(l==0&&m==0&&x==0) continue;
							int PP = P[2][l]*P[3][m]*P[5][x];
							for(int s:dp[i][j][k])
							{
								dp[i-l][j-m][k-x].insert(PP+s-1);
							}
						}
					}
				}
			}
		}
	}
	vector<int> big;
	for(int i=0;i<pf.size();i++)
	{
		if(pf[i].fi>=7)
		{
			for(int j=0;j<pf[i].se;j++) big.pb(pf[i].fi);
		}
	}
	int bigsiz = big.size();
	partitions[(1<<bigsiz)-1].insert({{}});
	vector<int> prod((1<<bigsiz),1);
	for(int i=0;i<(1<<bigsiz);i++)
	{
		for(int j=0;j<bigsiz;j++)
		{
			if(i&(1<<j)) prod[i]*=big[j];
		}
	}
	for(int i=(1<<bigsiz)-1;i>=0;i--)
	{
		for(int j=1;j<=i;j++)
		{
			if((j&i)==j)
			{
				for(auto S:partitions[i])
				{
					multiset<int> S2 = S; S2.insert(prod[j]);
					partitions[i^j].insert(S2);
				}
			}
		}
	}
	//now we got the set of all partitions in partitions[0]
	for(auto S:partitions[0])
	{
		solve(S, a, b, c);
	}
	cout<<ans.size()<<'\n';
	for(int v:ans) cout<<v<<' ';
	cout<<'\n';
}	

Compilation message (stderr)

toy.cpp: In function 'void solve(std::multiset<int>, int, int, int)':
toy.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z=0;z<=cur.size();z++)
              ~^~~~~~~~~~~~
toy.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int z=0;z<vec.size();z++)
              ~^~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:136:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pf.size();i++)
              ~^~~~~~~~~~
toy.cpp:145:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pf.size();i++)
              ~^~~~~~~~~~
toy.cpp:177:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pf.size();i++)
              ~^~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 21 / 21