Submission #536883

#	Time	Username	Problem	Language	Result	Execution time	Memory
536883		squiddy	Toys (CEOI18_toy)	C++14	79 / 100	4768 ms	262144 KiB

toy

#include <bits/stdc++.h>
#define fast_input ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
#define ii pair<int, int>
#define iii pair<int, ii>
#define ll long long
#define ull unsigned long long
#define pq priority_queue
#define FOR(v, s, e) for (int v = s; v < e; v++)
#define FOR_REV(v, s, e) for (int v = e - 1; v >= s; v--)
#define make_ii(a, b) make_pair(a, b)
#define make_iii(a, b, c) make_pair(a, make_pair(b, c))
#define fi first
#define se second
//#define int long long

int n, n_mod, fac = 2, ct;
vector<ii> pfac;
vector<int> factors;
vector<vector<ii>> adj_list;
set<int> answers;

void create_tree(int curr, int l_idx, int curr_idx) {
    if (adj_list.size() <= curr_idx) adj_list.resize(curr_idx + 1);
    if (curr == n) return;
    FOR(i, l_idx, factors.size()) {
        int factor = factors[i];
        int new_factor = curr * factor;
        if (curr > n / factor) return;
        if (n % new_factor == 0 && (n / new_factor >= factor || n == new_factor)) {
            int nidx = adj_list.size() + 1;
            adj_list[curr_idx].emplace_back(factor, nidx);
            create_tree(new_factor, i, nidx);
        }
    }
}

void dp_factors(int idx, int curr) {
    if (idx == pfac.size()) {
        if (curr != 1) factors.push_back(curr);
        return;
    }
    ii factor = pfac[idx];
    int c_exp = 1;
    FOR(i, 0, factor.se + 1) {
        dp_factors(idx + 1, curr * c_exp);
        c_exp *= factor.fi;
    }
}

void dfs(int nd, int c_sum, int c_total) {
    if (c_total == n) {
        answers.insert(c_sum);
        return;
    }
    for(ii node : adj_list[nd]) {
        dfs(node.se, c_sum + node.fi - 1, c_total * node.fi);
    }
}

int32_t main() {
    fast_input;
    cin >> n;
    n_mod = n;
    while (fac * fac <= n_mod) {
        ct = 0;
        for (;n_mod % fac == 0;ct++) {
            n_mod = n_mod / fac;
        }
        if (ct != 0) {
            pfac.emplace_back(fac, ct);
        }
        fac++;
    }
    if (n_mod != 1) pfac.emplace_back(n_mod, 1);
    // build factors
    dp_factors(0, 1);
    sort(factors.begin(), factors.end());
    create_tree(1, 0, 0);
    dfs(0, 0, 1);
    cout << answers.size() << '\n';
    for(int answer: answers) {
        cout << answer << ' ';
    }
}

Compilation message (stderr)

toy.cpp: In function 'void create_tree(int, int, int)':
toy.cpp:25:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     if (adj_list.size() <= curr_idx) adj_list.resize(curr_idx + 1);
      |         ~~~~~~~~~~~~~~~~^~~~~~~~~~~
toy.cpp:10:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(v, s, e) for (int v = s; v < e; v++)
......
   27 |     FOR(i, l_idx, factors.size()) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~        
toy.cpp:27:5: note: in expansion of macro 'FOR'
   27 |     FOR(i, l_idx, factors.size()) {
      |     ^~~
toy.cpp: In function 'void dp_factors(int, int)':
toy.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if (idx == pfac.size()) {
      |         ~~~~^~~~~~~~~~~~~~

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