Submission #161392

#	Time	Username	Problem	Language	Result	Execution time	Memory
161392		rama_pang	Toys (CEOI18_toy)	C++14	100 / 100	4345 ms	86752 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() {
    int N; scanf("%d", &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);
    printf("%d\n", (int)ans.size());
    for (auto i : ans) printf("%d ", i);
    printf("\n");
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:24:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N; scanf("%d", &N);
            ~~~~~^~~~~~~~~~

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