Submission #536916

#	Time	Username	Problem	Language	Result	Execution time	Memory
536916		squiddy	Toys (CEOI18_toy)	C++14	100 / 100	436 ms	11780 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;
vector<vector<int>> multiply;
set<int> answers;

void create_tree(int curr, int l_idx, int curr_idx) {
    if (curr == n) return;
    if (adj_list[curr_idx].size() != 0) return;
    FOR(i, l_idx, factors.size()) {
        int factor = factors[i];
        if (factor == 1) continue;
        int new_factor = curr * factor;
        if (curr > n / factor) return;
        if (n % new_factor == 0 && (n / new_factor >= factor || n == new_factor)) {
            int nidx = multiply[curr_idx][i];
            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()) {
        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, int l_factor) {
    if (c_total == n) {
        answers.insert(c_sum);
        return;
    }
    for(ii node : adj_list[nd]) {
        if (node.fi < l_factor) continue;
        dfs(node.se, c_sum + node.fi - 1, c_total * node.fi, max(node.fi, l_factor));
    }
}

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());
    multiply.resize(factors.size());
    FOR(i, 0, factors.size()) {
        multiply[i].resize(factors.size());
        FOR(j, 0, factors.size()) {
            if ((n / factors[i]) % factors[j] == 0) {
                multiply[i][j] = lower_bound(factors.begin(), factors.end(), factors[i] * factors[j]) - factors.begin();
            }
        }
    }
    adj_list.resize(factors.size());
    create_tree(1, 0, 0);
    dfs(0, 0, 1, 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: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++)
......
   28 |     FOR(i, l_idx, factors.size()) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~        
toy.cpp:28:5: note: in expansion of macro 'FOR'
   28 |     FOR(i, l_idx, factors.size()) {
      |     ^~~
toy.cpp: In function 'void dp_factors(int, int)':
toy.cpp:42: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]
   42 |     if (idx == pfac.size()) {
      |         ~~~~^~~~~~~~~~~~~~
toy.cpp: In function 'int32_t main()':
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++)
......
   84 |     FOR(i, 0, factors.size()) {
      |         ~~~~~~~~~~~~~~~~~~~~            
toy.cpp:84:5: note: in expansion of macro 'FOR'
   84 |     FOR(i, 0, factors.size()) {
      |     ^~~
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++)
......
   86 |         FOR(j, 0, factors.size()) {
      |             ~~~~~~~~~~~~~~~~~~~~        
toy.cpp:86:9: note: in expansion of macro 'FOR'
   86 |         FOR(j, 0, factors.size()) {
      |         ^~~

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