Submission #117190

#	Time	Username	Problem	Language	Result	Execution time	Memory
117190		teomrn	Toys (CEOI18_toy)	C++14	100 / 100	1062 ms	22332 KiB

toy

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

map <int, vector <int>> mp;

vector <int> & calc(int x)
{
	if (mp.find(x) != mp.end())
		return mp[x];

	vector <int> v = { x - 1 };
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			auto& q = calc(x / i);
			for (auto a : q)
				v.push_back(a + i - 1);
		}
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	mp[x] = v;
	return mp[x];
}

int main()
{
	//ifstream in("input.txt");
	//ofstream out("output.txt");

	int n;
	cin >> n;

	auto& x = calc(n);

	cout << x.size() << '\n';

	for (auto i : x)
		cout << i << ' ';
	cout << '\n';


	return 0;
}

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