Submission #305127

#	Time	Username	Problem	Language	Result	Execution time	Memory
305127		miss_robot	Toys (CEOI18_toy)	C++14	100 / 100	979 ms	79900 KiB

toy

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

int n;

unordered_map<string, unordered_set<int>> dp;
unordered_map<string, int> prod;
vector<int> p;
string c;

void smaller(int i, string& t, string& r){
	if(i == n){
		int s = prod[t]/prod[r]-1;
		unordered_set<int> *tmp1 = &dp[r], *tmp2 = &dp[t];
		for(int x : *tmp1) tmp2->insert(x+s);
		return;
	}
	for(int j = t[i]; j >= 0; j--){
		r.push_back(j);
		smaller(i+1, t, r);
		r.pop_back();
	}
}

void solve(int i, string& t){
	if(i == n){
		string r="";
		smaller(0, t, r);
		return;
	}
	for(int j = 0; j <= c[i]; j++){
		t.push_back(j);
		solve(i+1, t);
		t.pop_back();
	}
}

void pre(int i, int s, string &t){
	if(i == n){
		prod[t] = s;
		return;
	}
	for(int j = 0; j <= c[i]; j++){
		t.push_back(j);
		pre(i+1, s, t);
		s *= p[i];
		t.pop_back();
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n;
	int temp = sqrt(n);
	for(int i = 2; i <= temp; i++){
		if(!(n%i)) p.push_back(i), c.push_back(0);
		while(!(n%i)){
			c.back()++;
			n /= i;
		}
	}
	if(n > 1) p.push_back(n), c.push_back(1);
	n = p.size();
	string t(n, 0);
	dp[t].insert(0);
	t="";
	pre(0, 1, t);
	solve(0, t);
	vector<int> sol(dp[c].begin(), dp[c].end());
	sort(sol.begin(), sol.end());
	cout << sol.size() << "\n";
	for(int x : sol) cout << x << " ";
	cout << "\n";
}

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