Submission #161598

#	Time	Username	Problem	Language	Result	Execution time	Memory
161598		oolimry	Toys (CEOI18_toy)	C++14	100 / 100	4003 ms	91040 KiB

toy

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

int p;
bool comp(int x, int y){
	int xx = 0;
	int yy = 0;
	while(x % p == 0){
		xx++;
		x /= p;
	}
	while(y % p == 0){
		yy++;
		y /= p;
	}
	return xx < yy;
}

vector<vector<int> > adj;
set<int> memo[2000];
vector<int> factors;


int main(){
	int n;
	cin >> n;
	
	vector<int> primes;
	for(int i = 1;i <= min(n,100000);i++){
		if(n % i == 0){
			factors.push_back(i);
			factors.push_back(n/i);
		}
	}
	sort(factors.begin(),factors.end());
	factors.erase(unique(factors.begin(),factors.end()),factors.end());
	
	for(int x : factors){
		if(isPrime(x)) primes.push_back(x);
	}
	
	for(int pp : primes){
		p = pp;
		stable_sort(factors.begin(),factors.end(),comp);
	}
	for(int i = 0;i < (int) factors.size();i++){
		vector<int> v;
		adj.push_back(v);
	}
	memo[0].insert({0});
	for(int i = 0;i < (int) factors.size();i++){
		for(int j = i+1;j < (int) factors.size();j++){
			int x = factors[i];
			int y = factors[j];
			if(y % x == 0){
				if(true){
					adj[j].push_back(i);
				}
			}
		}
	}
	set<int> answer = memo[0];
	for(int i = 1;i < (int) factors.size();i++){
		for(int j : adj[i]){
			int c = factors[i] / factors[j] - 1;
			for(int v : memo[j]){
				memo[i].insert(v + c);
			}
		}
		answer = memo[i];
	}
	
	
	//sort(answer.begin(),answer.end());
	//answer.erase(unique(answer.begin(),answer.end()),answer.end());
	cout << answer.size() << "\n";
	for(int x : answer){
		cout << x << " ";
	}
	
}

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