Submission #558657

#	Time	Username	Problem	Language	Result	Execution time	Memory
558657		aryan12	Toys (CEOI18_toy)	C++17	100 / 100	725 ms	4460 KiB

toy

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

set<int> ans;
vector<int> divisors; // <= 30
vector<int> suffix_divisors;

void func(int idx, int num, int sum)
{
	ans.insert(sum + num - 1);
	// cout << "idx = " << idx << ", num = " << num << ", sum = " << sum << "\n";
	if(idx == divisors.size() || num < divisors[idx] * divisors[idx])
	{
		return;
	}
	if(num % divisors[idx] == 0)
	{
		func(idx, num / divisors[idx], sum + divisors[idx] - 1);
	}
	func(idx + 1, num, sum);
}

void Solve() 
{
	int n;
	cin >> n;
	int x = n;
	for(int i = 2; i <= sqrt(x); i++)
	{
		if(x % i == 0)
		{
			divisors.push_back(i);
		}
	}
	if(x != 1)
	{
		divisors.push_back(x);
	}
	sort(divisors.begin(), divisors.end());
	// for(int i = 0; i < divisors.size(); i++)
	// {
	// 	cout << divisors[i] << " ";
	// }
	// cout << "\n";
	// x = divisors.size();
	// suffix_divisors.resize(x);
	// suffix_divisors[x - 1] = divisors[x - 1];
	// for(int i = divisors.size() - 2; i >= 0; i--)
	// {
	// 	suffix_divisors[i] = suffix_divisors[i + 1] + divisors[i];
	// }
	func(0, n, 0);
	cout << ans.size() << "\n";
	for(auto i: ans)
	{
		cout << i << " ";
	}
	cout << "\n";
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

toy.cpp: In function 'void func(long long int, long long int, long long int)':
toy.cpp:15:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  if(idx == divisors.size() || num < divisors[idx] * divisors[idx])
      |     ~~~~^~~~~~~~~~~~~~~~~~

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