Submission #712589

#	Time	Username	Problem	Language	Result	Execution time	Memory
712589		600Mihnea	Toys (CEOI18_toy)	C++17	100 / 100	2185 ms	5220 KiB

toy

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <stack>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;

int n;
vector<int> dv;
vector<vector<int>> dvofdv;

int fnd(int x)
{
	int l = 0, r = (int)dv.size() - 1;
	while (l <= r)
	{
		int m = (l + r) / 2;
		if (dv[m] == x) return m;
		if (dv[m] < x) l = m + 1; else r = m - 1;
	}
	assert(0);
}

set<int> gustav;

void back(int x, int s, int mx)
{
	assert(x >= 2);
	gustav.insert(s + (x - 1));
	int p = fnd(x);
	for (auto& divizor : dvofdv[p])
	{
		if (divizor > mx) return;
		if (divizor > 1 && x / divizor > 1)
		{
			back(x / divizor, s + (divizor - 1), divizor);
		}
	}
}

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
	
	cin >> n;
	if (n == 1)
	{
		cout << "1\n";
		cout << "0\n";
		return 0;
	}
	for (int i = 1; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			dv.push_back(i);
			if (i * i == n) continue;
			dv.push_back(n / i);
		}
	}
	sort(dv.begin(), dv.end());
	dvofdv.resize((int)dv.size());
	for (int i = 0; i < (int)dv.size(); i++)
	{
		for (auto& x : dv)
		{
			if (x *(ll) x > dv[i]) break;
			if (dv[i] % x == 0)
			{
				dvofdv[i].push_back(x);
				if (x * x == dv[i]) continue;
				dvofdv[i].push_back(dv[i] / x);
			}
		}
		sort(dvofdv[i].begin(), dvofdv[i].end());
	}

	back(n, 0, n);
	cout << (int)gustav.size() << "\n";
	for (auto& x : gustav)
	{
		cout << x << " ";
	}
	cout << "\n";

	return 0;
}

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