Submission #1039142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039142		Trustfulcomic	Toys (CEOI18_toy)	C++14	59 / 100	5070 ms	604 KiB

toy

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

set<int> explored;

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;
}

bool inc_pows(vector<int>& cur, vector<pair<int,int>>& pf){
    for (int i = cur.size()-1; i >= 0; i--){
        if (cur[i] == pf[i].second){
            cur[i] = 0;
        } else {
            cur[i]++;
            return true;
        }
    }
    return false;
}

int int_pow(int x, int e){
    if (e == 0) return 1;
    int r = int_pow(x,e/2);
    if (e%2 == 1) return r*r*x;
    else return r*r;
}

void dfs(set<int>& res, vector<pair<int,int>> pf, int n, int cur){
    if (n == 1){
        res.insert(cur);
        return;
    }
    vector<int> cur_pows(pf.size(), 0);
    while(inc_pows(cur_pows, pf)){
        int divi = 1;
        for (int i = 0; i<pf.size(); i++){
            divi *= int_pow(pf[i].first, cur_pows[i]);
        }
        if (explored.find(divi) != explored.end()) continue;
        vector<pair<int,int>> next_pf;
        for (int i = 0; i<pf.size(); i++){
            next_pf.push_back({pf[i].first, pf[i].second-cur_pows[i]});
        }
        dfs(res, next_pf, n/divi, cur+divi-1);
        if (cur == 0) explored.insert(divi);
    }

}

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

    vector<pair<int,int>> p_fact;
    for (auto pii : p_factors){
        p_fact.push_back(pii);
    }

    set<int> res;
    dfs(res, p_fact, n, 0);
    cout << res.size() << endl;
    for (int i : res){
        cout << i << " ";
    }
    cout << endl;
}

Compilation message (stderr)

toy.cpp: In function 'void dfs(std::set<int>&, std::vector<std::pair<int, int> >, int, int)':
toy.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int i = 0; i<pf.size(); i++){
      |                         ~^~~~~~~~~~
toy.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i<pf.size(); i++){
      |                         ~^~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     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