Submission #464955

#	Time	Username	Problem	Language	Result	Execution time	Memory
464955		idk321	Toys (CEOI18_toy)	C++17	79 / 100	5049 ms	88160 KiB

toy

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

unordered_map<int, unordered_set<int>> possibleAt;

const int N = 10000000;

int divFac[N];


void getDivisors(vector<int>& divisors, vector<array<int, 2>>& freqs, int ind, int cur) {
    if (ind == freqs.size()) {
        divisors.push_back(cur);
        return;
    }
    for (int i = 0; i <= (freqs[ind][1]); i++) {
        getDivisors(divisors, freqs, ind + 1, cur);
        cur *= freqs[ind][0];
    }
}

void solveFor(int num) {
    if (possibleAt.find(num) != possibleAt.end()) return;
    possibleAt[num].insert(num - 1);
    if (num < N) {
        map<int, int> mapp;
        int cnum = num;
        while (cnum != 1) {
            mapp[divFac[cnum]]++;
            cnum /= divFac[cnum];
        }
        vector<int> divisors;
        vector<array<int, 2>> freqs;
        for (auto it = mapp.begin(); it != mapp.end(); it++) freqs.push_back({it->first, it->second});
        getDivisors(divisors, freqs, 0, 1);
        for (int divisor : divisors) {
            if (divisor != 1 && divisor <= num / 2) {
                solveFor(divisor);
                solveFor(num / divisor);
                for (auto it = possibleAt[divisor].begin(); it != possibleAt[divisor].end(); it++) {
                    for (auto it2 = possibleAt[num / divisor].begin(); it2 != possibleAt[num / divisor].end(); it2++) {
                        possibleAt[num].insert(*it + *it2);
                    }
                }
            }
        }
    } else {
        int cur = 2;
        while (cur * cur <= num) {
            if (num % cur == 0) {
                solveFor(cur);
                solveFor(num / cur);
                for (auto it = possibleAt[cur].begin(); it != possibleAt[cur].end(); it++) {
                    for (auto it2 = possibleAt[num / cur].begin(); it2 != possibleAt[num / cur].end(); it2++) {
                        possibleAt[num].insert(*it + *it2);
                    }
                }

            }
            cur++;
        }

    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);


    for (int i = 2; i < N; i++) {
        if (!divFac[i]) {
            divFac[i] = i;
            for (int j = i; j < N; j += i) {
                divFac[j] = i;
            }
        }
    }

    int n;
    cin  >> n;
    solveFor(n);
    cout << possibleAt[n].size() << "\n";
    vector<int> res(possibleAt[n].begin(), possibleAt[n].end());
    sort(res.begin(), res.end());
    for (int i : res) cout << i << " ";
    cout << "\n";
}

Compilation message (stderr)

toy.cpp: In function 'void getDivisors(std::vector<int>&, std::vector<std::array<int, 2> >&, int, int)':
toy.cpp:14:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if (ind == freqs.size()) {
      |         ~~~~^~~~~~~~~~~~~~~

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