Submission #161391

#	Time	Username	Problem	Language	Result	Execution time	Memory
161391		rama_pang	Toys (CEOI18_toy)	C++14	100 / 100	4195 ms	86776 KiB

toy

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

vector<int> factors;
map<int, set<int>> memo;

set<int> &solve(int n) {
    if (memo.count(n)) return memo[n];
    auto &ans = memo[n];
    if (n == 1) {
        ans.emplace(0);
    } else {
        for (auto &i : factors) {
            if (n % i) continue;
            auto &nxt = solve(n / i);
            for (auto &j : nxt) ans.emplace(j + i - 1);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int N; cin >> N;
    for (int i = 1; i * i <= N; i++) 
        if (N % i == 0) 
            factors.push_back(i), factors.push_back(N / i);
    
    sort(factors.begin(), factors.end());
    factors.resize(unique(factors.begin(), factors.end()) - factors.begin());
    factors.erase(factors.begin());

    set<int> &ans = solve(N);
    cout << ans.size() << "\n";
    for (auto i : ans) cout << i << " ";
    cout << "\n";
}

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