Submission #267109

#	Time	Username	Problem	Language	Result	Execution time	Memory
267109		peuch	Toys (CEOI18_toy)	C++17	79 / 100	5026 ms	8076 KiB

toy

#include<bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e4;
 
int n;
int cnt;
int v[MAXN], qnt[MAXN];
 
vector<int> ans;
map<int, vector<int> > dp, divisor;
 
void getDiv(int num);
void calcDP(int num);
 
int main(){
	scanf("%d", &n);
	calcDP(n);
	sort(ans.begin(), ans.end());
	printf("%lu\n", ans.size());
	for(int i = 0; i < ans.size(); i++)
		printf("%d ", ans[i]);
	printf("\n");
}
 
void getDiv(int num){
	if(num == 1) return;
	if(!divisor[num].empty()) return;
	vector<int> aux;
	aux.push_back(1);
	map<int, bool> marc;
	int x = num;
	for(int i = 2; i * i <= num; i++){
		if(x % i == 0){
			while(x % i) x /= i;
			getDiv(num / i);
			for(int j = 0; j < divisor[num / i].size(); j++){
				if(marc[divisor[num / i][j]]) continue;
				aux.push_back(divisor[num / i][j]);
				marc[divisor[num / i][j]] = 1;
			}
			for(int j = 0; j < divisor[num / i].size(); j++){
				if(marc[divisor[num / i][j] * i]) continue;
				aux.push_back(divisor[num / i][j] * i);
				marc[divisor[num / i][j] * i] = 1;
			}
			if(marc[i]) continue;
			aux.push_back(i);
			marc[i] = 1;
			divisor[num] = aux;
			return;
		}
	}
	aux.push_back(num);
	divisor[num] = aux;
}
 
void calcDP(int num){
	if(!dp[num].empty()){
		ans = dp[num];
		return;
	}
	getDiv(num);
	vector<int> aux = divisor[num];
	vector<int> ret;
	ret.push_back(num - 1);
	vector<int> aux1, aux2;
	map<int, bool> marc;
	for(int i = 0; i < aux.size(); i++){
		if(aux[i] == num || aux[i] == 1) continue;
		if(num / aux[i] < aux[i]) continue;
		calcDP(aux[i]);
		aux1 = ans;
		calcDP(num / aux[i]);
		aux2 = ans;
		for(int i1 = 0; i1 < aux1.size(); i1++){
			for( int i2 = 0; i2 < aux2.size(); i2++){
				if(marc[aux1[i1] + aux2[i2]]) continue;
				ret.push_back(aux1[i1] + aux2[i2]);
				marc[aux1[i1] + aux2[i2]] = 1;
			}
		}
	}
	ans = ret;
	dp[num] = ans;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < ans.size(); i++)
      |                 ~~^~~~~~~~~~~~
toy.cpp: In function 'void getDiv(int)':
toy.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    for(int j = 0; j < divisor[num / i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    for(int j = 0; j < divisor[num / i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp: In function 'void calcDP(int)':
toy.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int i = 0; i < aux.size(); i++){
      |                 ~~^~~~~~~~~~~~
toy.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i1 = 0; i1 < aux1.size(); i1++){
      |                   ~~~^~~~~~~~~~~~~
toy.cpp:77:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |    for( int i2 = 0; i2 < aux2.size(); i2++){
      |                     ~~~^~~~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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