Submission #331448

#	Time	Username	Problem	Language	Result	Execution time	Memory
331448		davitmarg	Toys (CEOI18_toy)	C++17	59 / 100	5061 ms	20560 KiB

toy

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <random>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 100005;

int n;
set<int> ans;
map<int, set<int>> dp[N];
map<int, int> used[N];

set<int> add(set<int> a,int d)
{
	set<int> s;
	for (auto it = a.begin(); it != a.end(); ++it)
		s.insert(*it + d);
	return s;
}


set<int> add(set<int> a, set<int> b)
{
	for (auto it = a.begin(); it != a.end(); ++it)
		b.insert(*it);
	return b;
}


int sq(int x)
{
	return sqrt(x);
}

void dfs(int num, int mx)
{
	if (mx > num)
	{
		used[mx][num] = used[num][num];
		dp[mx][num] = dp[num][num];
	}
	if (used[mx][num])
		return;
	used[mx][num] = 1;
	for (int i = 1; i * i <= num; i++)
	{
		if (num % i)
			continue;
		if (i <= mx && i != 1)
		{
			dfs(num / i, i);
			dp[mx][num] = add(dp[mx][num], add(dp[i][num / i], i - 1));
		}
		if (num / i <= mx && i != num / i)
		{
			dfs(i, num / i);
			dp[mx][num] = add(dp[mx][num], add(dp[num / i][i], num/i - 1));
		}
	}
}

int main()
{
	fastIO;
	cin >> n;
	used[1][1] = 1;
	dp[1][1].insert(0);

	for (int i = 1; i * i <= n; i++)
	{
		if (n % i)
			continue;

		int P = i;
		for (int j = 1; j * j <= n / P; j++)
		{
			if ((n / P) % j)
				continue;

			int p = j;

			if (p != 1 && p <= P)
			{
				dfs(n / P / p, p);
				ans = add(ans, add(dp[p][n / P / p], P + p - 2));
			}


			p = n / P / p;
			if (p != 1 && p <= P)
			{
				dfs(n / P / p, p);
				ans = add(ans, add(dp[p][n / P / p], P + p - 2));
			}

		}


		P = n / P;
		if (P * P == n)
			continue;
		for (int j = 1; j * j <= n / P; j++)
		{
			if ((n / P) % j)
				continue;

			int p = j;

			if (p != 1 && p <= P)
			{
				dfs(n / P / p, p);
				ans = add(ans, add(dp[p][n / P / p], P + p - 2));
			}

			p = n / P / p;
			if (p != 1 && p <= P)
			{
				dfs(n / P / p, p);
				ans = add(ans, add(dp[p][n / P / p], P + p - 2));
			}

		}
	}
	ans.insert(n - 1);
	cout << ans.size() << endl;
	for (auto it = ans.begin(); it != ans.end(); ++it)
		cout << (*it) << " ";
	cout << endl;
	return 0;
}
/*

3
1 2
1 3

*/

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