Submission #245269

#	Time	Username	Problem	Language	Result	Execution time	Memory
245269		eohomegrownapps	Toys (CEOI18_toy)	C++14	100 / 100	4985 ms	17248 KiB

toy

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

int factorp[100]; //(val, cnt)
int factorv[100];
int ptr = 0;

void calculateFactors(int n){
	int i = 2;
	while (i*i<=n){
		if (n%i==0){
			int fac = i;
			int cnt = 0;
			while (n%i==0){
				n/=i;
				cnt++;
			}
			factorp[ptr]=fac;
			factorv[ptr]=cnt;
			ptr++;
		}
		i+=1;
	}
	if (n!=1){
		factorp[ptr]=n;
		factorv[ptr]=1;
		ptr++;
	}
}

vector<int> vals;
int runningtotal = 0;

void recurse(int ind, int minval, int curval, bool zero){
	//cout<<ind<<" "<<curval<<" "<<minval<<" "<<runningtotal<<'\n';
	if (ind==ptr){
		//cout<<"reached end with "<<curval<<'\n';

		//have we used everything?
		/*bool yes = true;
		for (int i = 0; i<ptr; i++){
			if (factors[i].second!=0){
				yes=false;break;
			}
		}
		if (yes){*/
		if (zero){
			//we have.
			vals.push_back(runningtotal+curval-1);
			return;
		}
		if (curval==1){
			return;
			//don't care
		}
		//current total in curval
		if (curval<minval){
			return;
		}
		runningtotal+=curval-1;
		recurse(0, curval, 1, true);
		runningtotal-=curval-1;
		return;
	}
	int pv = 1;
	if (factorv[ind]!=0){
		zero=false;
	}
	int fvi = factorv[ind];
	for (int i = 0; i<=fvi; i++){
		//factorv[ind]-=i;
		recurse(ind+1, minval, curval*pv, zero);
		//factorv[ind]+=i;
		factorv[ind]--;
		pv*=factorp[ind];
	}
	factorv[ind]=fvi;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	calculateFactors(n);
	/*for (auto p : factors){
		cout<<p.first<<' '<<p.second<<'\n';
	}*/
	recurse(0,1,1,true);
	sort(vals.begin(),vals.end());
	vals.erase(unique(vals.begin(),vals.end()), vals.end());
	cout<<vals.size()<<'\n';
	for (int v : vals){
		cout<<v<<' ';
	}cout<<'\n';
}

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