Submission #245256

#	Time	Username	Problem	Language	Result	Execution time	Memory
245256		eohomegrownapps	Toys (CEOI18_toy)	C++14	79 / 100	5056 ms	66504 KiB

toy

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

vector<pair<int,int>> factors; //(val, cnt)

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++;
			}
			factors.push_back({fac,cnt});
		}
		i+=1;
	}
	if (n!=1){
		factors.push_back({n,1});
	}
}

vector<int> vals;

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

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

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,1);
	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';
}

Compilation message (stderr)

toy.cpp: In function 'void recurse(int, int, int, int)':
toy.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (ind==factors.size()){
      ~~~^~~~~~~~~~~~~~~~
toy.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i<factors.size(); i++){
                   ~^~~~~~~~~~~~~~~

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