Submission #823495

#	Time	Username	Problem	Language	Result	Execution time	Memory
823495		NK_	Toys (CEOI18_toy)	C++17	100 / 100	2946 ms	79404 KiB

toy

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	if (N == 1) {
		cout << 1 << nl;
		cout << 0 << nl;
		return 0;
	}

	vi D; unordered_map<int, int> I;
	for(int i = 1; i * i <= N; i++) {
		if (N % i == 0) {
			D.pb(i); 
			if (i*i != N) D.pb(N / i);
		}
	}

	int M = sz(D);
	sort(begin(D), end(D)); for(int i = 0; i < M; i++) I[D[i]] = i;

	V<unordered_set<int>> ans(M);

	function<void(int)> dnc = [&](int x) {
		int i = I[x];
		if (sz(ans[i])) return;

		ans[i] = {x - 1};
		for(int y = 2; y * y <= x; y++) {
			if (x % y == 0) {
				dnc(y); dnc(x / y);
				int ai = I[y], bi = I[x / y];

				// cout << "MERGE " << x << endl;
				// cout << y << " " << sz(ans[ai]) << endl;
				// cout << x / y << " " << sz(ans[bi]) << endl;
				// cout << endl;

				for(auto& a : ans[ai]) {
					for(auto& b : ans[bi]) {
						// cout << "-> " << a << " " << b << endl;
						ans[i].insert(a + b);
					}
				}
			}
		}

		// sort(begin(ans[i]), end(ans[i]));
		// ans[i].erase(unique(begin(ans[i]), end(ans[i])), end(ans[i]));
	};

	dnc(N);

	vi ANS(begin(ans.back()), end(ans.back()));
	sort(begin(ANS), end(ANS));
	cout << sz(ANS) << nl;
	for(auto& x : ANS) cout << x << " ";
	cout << nl;

    return 0;
}			

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