Submission #1039168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039168		Trustfulcomic	Toys (CEOI18_toy)	C++14	100 / 100	1189 ms	16980 KiB

toy

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

set<int> explored;
map<int, vector<int>> mem;

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

vector<int> dfs(vector<pair<int,int>> pf, int n){
    vector<int> res;
    if (n == 1){
        res = {0};
        return res;
    }

    set<int> bef_res;

    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 (mem.count(n/divi)){
            for (int i : mem[n/divi]){
                bef_res.insert(i + divi-1);
            }
            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]});
        }
        vector<int> cisla =  dfs(next_pf, n/divi);
        for (int i : cisla){
            bef_res.insert(i+divi-1);
        }
        mem[n/divi] = cisla;
    }

    for (int i : bef_res){
        res.push_back(i);
    }
    return res;

}

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

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

Compilation message (stderr)

toy.cpp: In function 'std::vector<int> dfs(std::vector<std::pair<int, int> >, int)':
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:66: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]
   66 |         for (int i = 0; i<pf.size(); i++){
      |                         ~^~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     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: 20 / 20
• Subtask 5: 21 / 21