Submission #409164

#	Time	Username	Problem	Language	Result	Execution time	Memory
409164		voldemort	Toys (CEOI18_toy)	C++17	100 / 100	1299 ms	109900 KiB

toy

#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

vi findFac(int n) {
	vi fac;
	for (int i = 1; i*i <= n; i++) if ((n%i) == 0) {
		fac.push_back(i);
		if (n/i != i) fac.push_back(n/i);
	}
	return fac;
}

int main() {
#ifdef mlocal
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	
#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	
	vi fac = findFac(n);
	sort(fac.begin(), fac.end());
	
	gp_hash_table<int, int> mp;
	
	int fs = fac.size();
	for_(i, 0, fs) mp[fac[i]] = i;
	
	vector<vi> sums(fs);
	sums[0] = {0};
	
	for_(i, 1, fs) {
		vi f = findFac(fac[i]);
		
		for (auto temp: f) {
			for (auto s: sums[mp[fac[i]/temp]]) sums[i].push_back(s+temp-1);
		}
		
		sort(sums[i].begin(), sums[i].end());
		sums[i].resize(unique(sums[i].begin(), sums[i].end())-sums[i].begin());
	}
	
	cout << sums[fs-1].size() << endl;
	for (auto i: sums[fs-1]) cout << i << " ";
	cout << endl;
}

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