Submission #1039116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039116		Trustfulcomic	Toys (CEOI18_toy)	C++14	59 / 100	5037 ms	712 KiB

toy

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

vector<int> primes_to(int n){
    vector<bool> is_prime(n+1, true);
    is_prime[0] = false;
    is_prime[1] = false;

    vector<int> primes;

    for (int i = 0; i<=n; i++){
        if (!is_prime[i]) continue;
        primes.push_back(i);
        for (int j = 2; j*i <= n; j++){
            is_prime[j*i] = false;
        }
    }

    return primes;
}

void dfs(set<int>& res, vector<int> div, int n, int cur){
    if (n == 1){
        res.insert(cur);
        return;
    }
    for (int d : div){
        if (n % d == 0){
            dfs(res, div, n/d, cur+d-1);
        }
    }   
}

int main(){
    vector<int> primes = primes_to(sqrt(1000000000)+1);
    int n; cin >> n;
    int cpy_n = n;
    vector<int> p_factors;
    for (int i = 0; i<primes.size() && cpy_n > 1; i++){
        while (cpy_n % primes[i] == 0){
            p_factors.push_back(primes[i]);
            cpy_n /= primes[i];
        }
    }
    if (cpy_n != 1){
        p_factors.push_back(cpy_n);
    }

    set<int> divis;
    divis.insert(1);
    for (int p : p_factors){
        vector<int> to_add;
        for (int d : divis){
            to_add.push_back(d*p);
        }
        for (int i : to_add){
            divis.insert(i);
        }
    }
    vector<int> div;
    for (int d : divis){
        if (d != 1) div.push_back(d);
    }
    
    set<int> res;
    dfs(res, div, n, 0);
    cout << res.size() << endl;
    for (int i : res){
        cout << i << " ";
    }
    cout << endl;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i<primes.size() && cpy_n > 1; i++){
      |                     ~^~~~~~~~~~~~~~

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