Submission #847749

#	Time	Username	Problem	Language	Result	Execution time	Memory
847749		Dec0Dedd	Toys (CEOI18_toy)	C++14	100 / 100	1804 ms	101548 KiB

toy

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
 
int n;
vector<int> divs;

unordered_map<int, vector<int>> dp;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    scanf("%d", &n);
 
    for (int i=2; i*i<=n; ++i) {
        if (n%i == 0) divs.push_back(i), divs.push_back(n/i);
    } divs.push_back(n);
    sort(divs.begin(), divs.end());
    divs.erase(unique(divs.begin(), divs.end()), divs.end());

    if (n == 1) {
        printf("1\n0\n");
        return 0;
    }
 
    dp[1]={0};
    set<int> st; st.insert(1);
    for (auto i : st) {
        sort(dp[i].begin(), dp[i].end());
        dp[i].erase(unique(dp[i].begin(), dp[i].end()), dp[i].end());

        for (auto u : divs) {
            if (i > n/u) break;
            if (n%(i*u)) continue;
            for (auto k : dp[i]) dp[i*u].push_back(k+u-1), st.insert(i*u);
        }

        if (i < n) vector<int>().swap(dp[i]);
    }

    printf("%d\n", (int)dp[n].size());
    for (auto u : dp[n]) printf("%d ", u);
    printf("\n");
}

Compilation message (stderr)

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

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