Submission #1168298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168298		altern23	Toys (CEOI18_toy)	C++20	79 / 100	5094 ms	61564 KiB

toy

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;

vector<ll> ans;
map<pii, ll> mp;

vector<ll> D;

void calc(ll idx, ll sum){
    if(mp.count({idx, sum})) return;
    mp[{idx, sum}] = 1;
    if(idx == 1){
        ans.push_back(sum);
        return;
    }
    for(auto i : D){
        if(i > idx) break;
        if(idx % i) continue;
        if(i != 1) calc(idx / i, sum + i - 1);
        if(idx / i != 1 && i != idx / i){
            calc(idx / (idx / i), sum + idx / i - 1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n; cin >> n;
        for(ll i = 1; i * i <= n; i++){
            if(n % i) continue;
            D.push_back(i);
            if(i != n / i) D.push_back(n / i);
        }
        sort(D.begin(), D.end());
        D.erase(unique(D.begin(), D.end()), D.end());

        calc(n, 0);

        sort(ans.begin(), ans.end());
        ans.erase(unique(ans.begin(), ans.end()), ans.end());
        cout << (int)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: 0 / 21