Submission #1119587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119587		vjudge1	Toys (CEOI18_toy)	C++17	100 / 100	1225 ms	70732 KiB

toy

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second

using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 2e5 + 5;

int n;
vector <int> p;
unordered_map <int, int> was;
unordered_map <int, map <int, int> > mp;

void solve(int x, int r) {
	if (x == 1)
		return;
	if (was.count(x))
		return;
	was[x] = 1;
	for (int i = r; i >= 0; i--) {
		if (x % p[i] == 0) {
			solve(x / p[i], i);
			for (auto sum : mp[x / p[i]]) {
				mp[x][sum.f + p[i] - 1] = 1;
			}
			
		}
	}
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	mp[1][0] = 1;
	cin >> n;
	for (int i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			p.pb(i);
			if (i * i != n)
				p.pb(n / i);
		}
	}
	p.pb(n);
	sort(all(p));
	solve(n, sz(p) - 1);
	cout << sz(mp[n]) << '\n';
	for (auto x : mp[n])
		cout << x.f << ' ';
	return 0;
}

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