Submission #823452

#TimeUsernameProblemLanguageResultExecution timeMemory
823452NK_Toys (CEOI18_toy)C++17
79 / 100
2207 ms262144 KiB
// 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;

	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<vi> ans(M);

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

		ans[i] = {x - 1};
		for(int y = 1; 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]) ans[i].pb(a + b);
			}
		}

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

	dnc(N);

	cout << sz(ans.back()) << nl;
	for(auto& x : ans.back()) cout << x << " ";
	cout << nl;

    return 0;
}			
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...