Submission #267137

#	Time	Username	Problem	Language	Result	Execution time	Memory
267137		peuch	Toys (CEOI18_toy)	C++17	79 / 100	5017 ms	8532 KiB

toy

#include<bits/stdc++.h>
#include<unordered_map>
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;
unordered_map<int, vector<int> > dp, divisor;
 
void getDiv(int num);
void calcDP(int num);
int fexp(int a, int exp);

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(!divisor[num].empty()) return;
	divisor[num].push_back(1);
	if(num == 1) return;
	int x = num;
	int aux = 0;
	vector<int> m, q;
	for(int i = 2; i * i <= num; i++){
		if(x % i == 0){
			int exp = 0;
			while(x % i == 0) aux++, exp++, x /= i;
			m.push_back(i);
			q.push_back(exp);
		}
	}
	if(x != 1){
		m.push_back(x);
		q.push_back(1);
		aux++;
	}
	if(aux == 1){
		divisor[num].push_back(num);
		return;
	}
	if(m.size() == 1){
		getDiv(num / m[0]);
		divisor[num] = divisor[num / m[0]];
		divisor[num].push_back(num);	
		return;
	}
	int mult = 1;
	int aux1 = 0;
	for(int i = 0; i < m.size() - 1; i++){
		aux1 += q[i];
		mult *= fexp(m[i], q[i]);
		if(2 * aux1 >= aux){
			getDiv(mult);
			getDiv(num / mult);
			for(int j = 0; j < divisor[mult].size(); j++){
				for(int k = 0; k < divisor[num / mult].size(); k++){
					if(k == 0 && j == 0) continue;
					int val = divisor[mult][j] * divisor[num / mult][k];
					divisor[num].push_back(val);
				}
			}
			return;
		}
	}
	aux1 = 0;
	mult = 1;
	for(int i = m.size() - 1; i >= 0; i--){
		aux1 += q[i];
		mult *= fexp(m[i], q[i]);
		if(2 * aux1 >= aux){
			getDiv(mult);
			getDiv(num / mult);
			for(int j = 0; j < divisor[mult].size(); j++){
				for(int k = 0; k < divisor[num / mult].size(); k++){
					if(k == 0 && j == 0) continue;
					int val = divisor[mult][j] * divisor[num / mult][k];
					divisor[num].push_back(val);
				}
			}
			return;
		}
	}
}
 
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;
}

int fexp(int a, int exp){
	int ret = 1;
	for(int k = 30; k >= 0; k--){
		ret *= ret;
		if((1 << k) & exp) ret *= a;
	}
	return ret;
}

Compilation message (stderr)

toy.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
toy.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
toy.cpp: In function 'int main()':
toy.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0; i < ans.size(); i++)
      |                 ~~^~~~~~~~~~~~
toy.cpp: In function 'void getDiv(int)':
toy.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i = 0; i < m.size() - 1; i++){
      |                 ~~^~~~~~~~~~~~~~
toy.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for(int j = 0; j < divisor[mult].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
toy.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int k = 0; k < divisor[num / mult].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for(int j = 0; j < divisor[mult].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
toy.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int k = 0; k < divisor[num / mult].size(); k++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp: In function 'void calcDP(int)':
toy.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int i = 0; i < aux.size(); i++){
      |                 ~~^~~~~~~~~~~~
toy.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for(int i1 = 0; i1 < aux1.size(); i1++){
      |                   ~~~^~~~~~~~~~~~~
toy.cpp:119:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |    for( int i2 = 0; i2 < aux2.size(); i2++){
      |                     ~~~^~~~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~

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