Submission #124475

#TimeUsernameProblemLanguageResultExecution timeMemory
124475RafikHachanaToys (CEOI18_toy)C++14
100 / 100
1796 ms22496 KiB
#include <bits/stdc++.h>
using namespace std;
 
vector<int> s;
//vector<int> v;
unordered_map<int,vector<int> > m;
unordered_map<int,int> val;
 
vector<int> dp(int n,int x)
{
	if(n==1)
	{
		vector<int> tmp;
		tmp.push_back(x);
		return tmp;
	}
	vector<int> tmp;
	if(val.find(n)!=val.end())
	{
		for(auto it:m[n]) tmp.push_back(it-val[n]+x);
			return tmp;
	}
	for(int i=1;i<=sqrt(n);i++)
	{
		if(n%i==0)
		{
			if(i!=1)
			{
				vector<int> t1 = dp(n/i,x+i-1);
				for(auto it:t1) tmp.push_back(it);
			} 
			vector<int> t2 = dp(i,x+n/i-1);
			for(auto it:t2) tmp.push_back(it);
		}
	}
	sort(tmp.begin(),tmp.end());
	auto last = unique(tmp.begin(),tmp.end());
	tmp.erase(last,tmp.end());
	val[n] = x;
	m[n] = tmp;
	return tmp;
}
 
int main()
{
	int n;
	cin>>n;
	s = dp(n,0);
	cout<<s.size()<<endl;
	for(auto it:s) cout<<it<<" ";
		cout<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...