Submission #825348

#	Time	Username	Problem	Language	Result	Execution time	Memory
825348		alex_2008	Toys (CEOI18_toy)	C++14	100 / 100	2751 ms	79960 KiB

toy

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int NN = 2e3 + 10;
int main() {
	int n;
	cin >> n;
	if (n == 1) {
		cout << "1\n";
		cout << "0\n";
		return 0;
	}
	vector <int> v;
	int j;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) v.push_back(i);
		if (i * i < n) j = i;
	} 
	for (int i = j; i >= 1; i--) {
		if (n % i == 0) {
			v.push_back(n / i);
		}
	}
	map <int, int> yp;
	unordered_map <int, int> mp;
	int N = (int)v.size();
	for (int i = 1; i <= (int)v.size(); i++) {
		mp[i] = v[i - 1];
		yp[v[i - 1]] = i;
	}
	vector<unordered_map<int, bool>> ans(N + 1);
	ans[1] = { { 0, true} };
	for (int i = 1; i < N; i++) {
		for (int j = 2; j <= N - i + 1; j++) {
			if (yp.find(mp[i] * mp[j]) != yp.end()) {
				for (auto it : ans[i]) {
					ans[yp[mp[i] * mp[j]]][it.first + mp[j] - 1] = true;
				}
			}
		}
	}
	vector <int> vv; 
	for (auto &it : ans[N]) {
		vv.push_back(it.first);
	}
	sort(vv.begin(), vv.end());
	cout << (int)vv.size() << "\n";
	for (auto it : vv) {
		cout << it << " ";
	}
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:19:6: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   19 |  int j;
      |      ^

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