| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 267136 |
2020-08-15T21:26:51 Z |
peuch |
Toys (CEOI18_toy) |
C++17 |
|
0 ms |
256 KB |
#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++){
printf("%d\n", aux[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
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:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i1 = 0; i1 < aux1.size(); i1++){
| ~~~^~~~~~~~~~~~~
toy.cpp:120:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | 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);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
