Submission #225770

#	Time	Username	Problem	Language	Result	Execution time	Memory
225770		kshitij_sodani	Toys (CEOI18_toy)	C++17	79 / 100	5073 ms	70128 KiB

toy

#include <iostream>
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;

#define pb push_back
#define a first
#define b second
typedef int llo;
set<int> fin;
map<pair<int,int>,int> kk;
vector<llo> fac2[100000];
map<llo,llo> ss;
int rec(int nn,int su=0,int ma=0){
	if(kk[{nn,su}]==0){
		kk[{nn,su}]=1;
		if(nn==1){
			fin.insert(su);
		}
		else{
			for(int kk=fac2[ss[nn]].size()-1;kk>=0;kk--){
				int jj=fac2[ss[nn]][kk];
				if(jj==1){
					continue;
				}
				if(jj>=ma){
					rec(nn/jj,su+jj-1,jj);
				}
				else{
					break;
				}
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	llo n;
	cin>>n;
	vector<llo> fac;
	fac.clear();
	llo i=1;
	while(i*i<=n){
		if(n%i==0){
			fac.pb(i);
		
			fac.pb(n/i);
		//	cout<<n<<" "<<i<<endl;
		}
		i+=1;
	}
	
	llo k=-1;
	
	//n^(2/3) finding factors
	for(llo kk=0;kk<fac.size();kk++){
		llo nn=fac[kk];
		k+=1;
		ss[nn]=k;
		llo i=1;
		while(i*i<=n){
			if(nn%i==0){
				fac2[kk].pb(i);
				fac2[kk].pb(nn/i);
		//	cout<<n<<" "<<i<<endl;
		}
		i+=1;
	}

	for(int i=0;i<fac.size();i++){
		sort(fac2[i].begin(),fac2[i].end());
	}
		/*for(auto i:fac){
			if(nn%i==0){
				fac2[kk].pb(i);
			}
			i+=1;
		}*/
	}
	rec(n,0);
	//31*(n^1/3)*(n^(1/3))

/*	for(llo i=0;i<31;i++){
		for(llo j=0;j<fac.size();j++){
			if(i==0){
				dp[j][i].insert(fac[j]-1);
			}
			else{
				for(auto jj:fac2[j]){
					if(jj==1 or jj==fac[j]){
						continue;
					}
					for(auto kk:dp[ss[fac[j]/jj]][i-1]){
						dp[j][i].insert(kk+jj-1);
					}
				}
			}
		}
	}
	set<llo> ans;
	for(llo i=0;i<31;i++){
		for(auto jj:dp[ss[n]][i]){
			ans.insert(jj);
		}
	}*/
	cout<<fin.size()<<endl;

	for(auto ans2:fin){	
		cout<<ans2<<" ";
	}
	cout<<endl;;


	return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int rec(int, int, int)':
toy.cpp:35:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
toy.cpp: In function 'int main()':
toy.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo kk=0;kk<fac.size();kk++){
               ~~^~~~~~~~~~~
toy.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<fac.size();i++){
              ~^~~~~~~~~~~

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