oj.uz

Submission #464958

# Submission time Handle Problem Language Result Execution time Memory
464958 2021-08-14T15:09:33 Z idk321 Toys (CEOI18_toy) C++17
0 / 100
 99 ms 19868 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

unordered_map<int, unordered_set<int>> possibleAt;

const int N = 5000000;

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]) / 2; 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

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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19860 KB Output is correct
2 Correct 99 ms 19864 KB Output is correct
3 Correct 91 ms 19788 KB Output is correct
4 Correct 95 ms 19788 KB Output is correct
5 Correct 93 ms 19792 KB Output is correct
6 Incorrect 98 ms 19868 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19860 KB Output is correct
2 Correct 99 ms 19864 KB Output is correct
3 Correct 91 ms 19788 KB Output is correct
4 Correct 95 ms 19788 KB Output is correct
5 Correct 93 ms 19792 KB Output is correct
6 Incorrect 98 ms 19868 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19860 KB Output is correct
2 Correct 99 ms 19864 KB Output is correct
3 Correct 91 ms 19788 KB Output is correct
4 Correct 95 ms 19788 KB Output is correct
5 Correct 93 ms 19792 KB Output is correct
6 Incorrect 98 ms 19868 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19860 KB Output is correct
2 Correct 99 ms 19864 KB Output is correct
3 Correct 91 ms 19788 KB Output is correct
4 Correct 95 ms 19788 KB Output is correct
5 Correct 93 ms 19792 KB Output is correct
6 Incorrect 98 ms 19868 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 19860 KB Output is correct
2 Correct 99 ms 19864 KB Output is correct
3 Correct 91 ms 19788 KB Output is correct
4 Correct 95 ms 19788 KB Output is correct
5 Correct 93 ms 19792 KB Output is correct
6 Incorrect 98 ms 19868 KB Output isn't correct
7 Halted 0 ms 0 KB -