Submission #426344

#	Time	Username	Problem	Language	Result	Execution time	Memory
426344		linkret	Toys (CEOI18_toy)	C++14	100 / 100	1464 ms	24784 KiB

toy

#include <bits/stdc++.h>
using namespace std;
map <int, int> m; vector <int> dp [100000]; vector <int> dj; int n;
vector <int> rek (int x){
	//cout << x << endl;
	vector <int> s;
	if (dp[m[x]].size()!=0) return dp[m[x]];
	if (x==1) return {0};
	for (int i=0; i<dj.size(); i++){
		if (sqrt(x)<dj[i]) break;
		else if (x%dj[i]==0){
			vector <int> s3, s2;
			if (i!=0){
				s2=rek (x/dj[i]);
				for (auto it:s2) s3.push_back (it+dj[i]-1);
			}
			s2=rek (x/(x/dj[i]));
			for (auto it:s2) s3.push_back (it+(x/dj[i])-1);
			for (auto e : s3)
				s.push_back(e);
		}
	}
	sort (s.begin(), s.end());
	s.erase(unique(s.begin(), s.end()), s.end());
	return dp [m[x]]=s;
}
int main(){
	cin >> n; int now=0;
	dj.push_back(n);
	for (int i=1; i<=sqrt (n); i++){
		if (n%i==0){
			m [i]=now; m[n/i]=now+1; now+=2;
			dj.push_back(i); dj.push_back(n/i);
		}
	}
	sort (dj.begin(), dj.end());
	vector <int> ans = rek (n);
	cout << ans.size() << endl;
	for (auto it:ans) cout << it << " ";
}

Compilation message (stderr)

toy.cpp: In function 'std::vector<int> rek(int)':
toy.cpp:9:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |  for (int i=0; i<dj.size(); i++){
      |                ~^~~~~~~~~~

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