Submission #480734

#	Time	Username	Problem	Language	Result	Execution time	Memory
480734		wiwiho	Toys (CEOI18_toy)	C++14	100 / 100	1400 ms	128876 KiB

toy

#include<bits/stdc++.h>

#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {\
    for(auto pv : a) b << pv << " ";\
    b << "\n";\
}

using namespace std;

typedef long long ll;

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

    int n;
    cin >> n;

    vector<int> f;
    for(int i = 1; (ll)i * i <= n; i++){
        if(n % i) continue;
        f.eb(i);
        if(n / i != i) f.eb(n / i);
    }

    lsort(f);

    int m = f.size();
    vector<vector<int>> dp(m);

    dp[0].eb(0);

    for(int i = 0; i < m; i++){
        int now = f[i];
        lsort(dp[i]);
        uni(dp[i]);
        for(int j : f){
            if(j == 1) continue;
            if(n % ((ll)now * j)) continue;
            int id = lower_bound(iter(f), now * j) - f.begin();
            for(int k : dp[i]) dp[id].eb(k + j - 1);
        }
    }

    cout << dp[m - 1].size() << "\n";
    printv(dp[m - 1], cout);

    return 0;
}

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