Submission #267086

#	Time	Username	Problem	Language	Result	Execution time	Memory
267086		peuch	Toys (CEOI18_toy)	C++17	59 / 100	5066 ms	21172 KiB

toy

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

const int MAXN = 2e4;

int n;
int cnt;
int v[MAXN], qnt[MAXN];

vector<int> divisor;
set<int> ans;
map<int, set<int> > dp;

void getDiv(int num);
void bt(int cur, int val, int num);
void calcDP(int num);

int main(){
	scanf("%d", &n);
	calcDP(n);
	printf("%lu\n", ans.size());
	set<int> :: iterator it;
	for(it = ans.begin(); it != ans.end(); it++){
		printf("%d ", *it);
	}
	printf("\n");
}

void getDiv(int num){
	memset(v, 0, sizeof(v));
	memset(qnt, 0, sizeof(qnt));
	divisor.clear();
	cnt = 0;
	int x = num;
	for(int i = 2; i * i <= n; i++){
		if(x % i == 0){
			v[++cnt] = i;
			while(x % i == 0) qnt[cnt]++, x /= i;
		} 
	}
	bt(1, 1, num);	
}

void calcDP(int num){
	if(!dp[num].empty()){
		ans = dp[num];
		return;
	}
	getDiv(num);
	vector<int> aux = divisor;
	set<int> ret;
	set<int> :: iterator it1, it2;
	set<int> aux1, aux2;
	for(int i = 0; i < aux.size(); i++){
		calcDP(aux[i]);
		aux1 = ans;
		calcDP(num / aux[i]);
		aux2 = ans;
		for(it1 = aux1.begin(); it1 != aux1.end(); it1++)
			for(it2 = aux2.begin(); it2 != aux2.end(); it2++)
				ret.insert(*it1 + *it2);
	}
	ans = ret;
	ans.insert(num - 1);
	dp[num] = ans;
}

void bt(int cur, int val, int num){
	if(cur > cnt){
		if(val == 1 || val == num) return;
		divisor.push_back(min(val, num / val));
		return;
	}
	int aux = 1;
	for(int i = 0; i <= qnt[cur]; i++){
		bt(cur + 1, val * aux, num);
		aux *= v[cur];
	}
}

Compilation message (stderr)

toy.cpp: In function 'void calcDP(int)':
toy.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < aux.size(); i++){
      |                 ~~^~~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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