Submission #74583

#	Time	Username	Problem	Language	Result	Execution time	Memory
74583		szawinis	Toys (CEOI18_toy)	C++17	100 / 100	4459 ms	87560 KiB

toy

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> divs;
map<int, set<int> > dp;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 2; i <= sqrt(n); i++) if(n % i == 0) {
		divs.push_back(i);
		divs.push_back(n/i);
	}
	divs.push_back(n);
	sort(divs.begin(), divs.end());
	divs.resize(unique(divs.begin(), divs.end()) - divs.begin());
	for(int d: divs) dp[d].insert(d - 1);
	for(int i = 0; i < divs.size(); i++) {
		for(int j = 0; j < i; j++) if(divs[i] % divs[j] == 0) {
			for(int x: dp[divs[j]]) dp[divs[i]].insert(x + divs[i] / divs[j] - 1);
		}
	}
	cout << dp[n].size() << endl;
	for(int x: dp[n]) cout << x << ' ';
	cout << endl;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:19:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < divs.size(); i++) {
                 ~~^~~~~~~~~~~~~

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