Submission #203559

#	Time	Username	Problem	Language	Result	Execution time	Memory
203559		PeppaPig	Toys (CEOI18_toy)	C++14	100 / 100	1459 ms	110000 KiB

toy

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> fac;

int main() {
    scanf("%d", &n);

    for(int i = 1; i * i <= n; i++) if(n % i == 0) {
        fac.emplace_back(i);
        if(i * i != n) fac.emplace_back(n / i);
    }
    sort(fac.begin(), fac.end());

    vector<vector<int> > dp(fac.size());
    dp[0].emplace_back(0);

    for(int i = 1; i < fac.size(); i++) {
        for(int j = 0; j < i; j++) {
            if(fac[i] % fac[j] != 0) continue;
            for(int x : dp[j]) dp[i].emplace_back(x + fac[i] / fac[j] - 1);
        }
        sort(dp[i].begin(), dp[i].end());
        dp[i].resize(unique(dp[i].begin(), dp[i].end()) - dp[i].begin());
    }
    printf("%d\n", (int)dp.back().size());
    for(int x : dp.back()) printf("%d ", x);
    printf("\n");

    return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < fac.size(); i++) {
                    ~~^~~~~~~~~~~~
toy.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~

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