Submission #966141

#	Time	Username	Problem	Language	Result	Execution time	Memory
966141		Tob	Toys (CEOI18_toy)	C++14	100 / 100	2786 ms	82100 KiB

toy

#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;
 
typedef pair <ll, ll> pii;
 
const int C = 5007;
 
int cnt, dc;
vector <int> di[C];
unordered_map <int, int> did;
unordered_map <ll, int> sd;
vector <int> res;
 
inline ll Enc(ll x, ll y) {
	return (x << 32) + y;
}
 
void rek(int n, int sum) {
	int o = sd[Enc(n, sum)];
	if (o) return;
	sd[Enc(n, sum)] = 1;
	if (n == 1) {
		res.pb(sum);
		return;
	}
	int x = did[n];
	for (int y : di[x]) {
		rek(n/y, sum + y - 1);
	}
}
 
int main () {
	FIO;
	int n; cin >> n;
	for (int i = 1; i*i <= n; i++) {
		if (n % i) continue;
		did[i] = ++dc;
		for (int j = 2; j*j <= i; j++) {
			if (i % j) continue;
			di[dc].pb(j);
			if (j * j != i) di[dc].pb(i/j);
		}
		di[dc].pb(i);
		if (i * i != n) {
			did[n/i] = ++dc;
			for (int j = 2; j*j <= n/i; j++) {
				if ((n/i) % j) continue;
				di[dc].pb(j);
				if (j * j != n/i) di[dc].pb(n/i/j);
			}
			di[dc].pb(n/i);
		}
	}
	
	rek(n, 0);
	
	sort(all(res));
	cout << res.size() << "\n";
	
	for (auto it : res) cout << it << " ";
 
	return 0;
}

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