Submission #267115

#	Time	Username	Problem	Language	Result	Execution time	Memory
267115		peuch	Toys (CEOI18_toy)	C++17	59 / 100	5062 ms	5300 KiB

toy

#include<bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
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(dp[n].begin(), dp[n].end());
	printf("%lu\n", dp[n].size());
	for(int i = 0; i < dp[n].size(); i++)
		printf("%d ", dp[n][i]);
	printf("\n");
}
 
void getDiv(int num){
	if(!divisor[num].empty()) return;
	if(num == 1){
		divisor[num].push_back(1);
		return;
	}
	map<int, bool> marc;
	for(int i = sqrt(num); i > 1; i--){
		if(num == i) continue;
		if(num % i) continue;
		if(divisor[i].empty() || divisor[num / i].empty()) continue;
		getDiv(i);
		getDiv(num / i);
		for(int j = 0; j < divisor[i].size(); j++){
			for(int k = 0; k < divisor[num / i].size(); k++){
				int val = divisor[i][j] * divisor[num / i][k];
				if(marc[val]) continue;
				marc[val] = 1;
				divisor[num].push_back(val);
			}
		}
		return;
	}
	for(int i = sqrt(num); i > 1; i--){
		if(num == i) continue;
		if(num % i) continue;
		if(divisor[i].empty() && divisor[num / i].empty()) continue;
		getDiv(i);
		getDiv(num / i);
		for(int j = 0; j < divisor[i].size(); j++){
			for(int k = 0; k < divisor[num / i].size(); k++){
				int val = divisor[i][j] * divisor[num / i][k];
				if(marc[val]) continue;
				marc[val] = 1;
				divisor[num].push_back(val);
			}
		}
		return;
	}
	for(int i = sqrt(num); i > 1; i--){
		if(num == i) continue;
		if(num % i) continue;
		getDiv(i);
		getDiv(num / i);
		for(int j = 0; j < divisor[i].size(); j++){
			for(int k = 0; k < divisor[num / i].size(); k++){
				int val = divisor[i][j] * divisor[num / i][k];
				if(marc[val]) continue;
				marc[val] = 1;
				divisor[num].push_back(val);
			}
		}
		return;
	}
	divisor[num].push_back(1);
	divisor[num].push_back(num);
}
 
void calcDP(int num){
	if(!dp[num].empty()) return;
	getDiv(num);
	dp[num].push_back(num - 1);
	map<int, bool> marc;
	for(int i = 0; i < divisor[num].size(); i++){
		if(divisor[num][i] == num || divisor[num][i] == 1) continue;
		if(num / divisor[num][i] < divisor[num][i]) continue;
		int aux1, aux2;
		calcDP(divisor[num][i]);
		aux1 = divisor[num][i];
		calcDP(num / divisor[num][i]);
		aux2 = num / divisor[num][i];
		for(int i1 = 0; i1 < dp[aux1].size(); i1++){
			for(int i2 = 0; i2 < dp[aux2].size(); i2++){
				if(marc[dp[aux1][i1] + dp[aux2][i2]]) continue;
				dp[num].push_back(dp[aux1][i1] + dp[aux2][i2]);
				marc[dp[aux1][i1] + dp[aux2][i2]] = 1;
			}
		}
	}
}

Compilation message (stderr)

toy.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
toy.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
toy.cpp: In function 'int main()':
toy.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0; i < dp[n].size(); i++)
      |                 ~~^~~~~~~~~~~~~~
toy.cpp: In function 'void getDiv(int)':
toy.cpp:42:20: 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[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~
toy.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for(int k = 0; k < divisor[num / i].size(); k++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j = 0; j < divisor[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~
toy.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int k = 0; k < divisor[num / i].size(); k++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int j = 0; j < divisor[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~
toy.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int k = 0; k < divisor[num / i].size(); k++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp: In function 'void calcDP(int)':
toy.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0; i < divisor[num].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
toy.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i1 = 0; i1 < dp[aux1].size(); i1++){
      |                   ~~~^~~~~~~~~~~~~~~~~
toy.cpp:101:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |    for(int i2 = 0; i2 < dp[aux2].size(); i2++){
      |                    ~~~^~~~~~~~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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