Submission #1155124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155124		mutse	Toys (CEOI18_toy)	C++20	100 / 100	2736 ms	4792 KiB

toy

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n;
vector<int> ans, now;
map<int, bool> ansDict;

void calculate(){
    int cnt = 0;
    for(auto i: now) cnt += i - 1;
    if(!ansDict[cnt]){
        ans.push_back(cnt);
        ansDict[cnt] = 1;
    }
}

// n의 소인수 중 divisor보다 크거나 같은 소인수를 찾는 dfs
void dfs(int n, int divisor){
    // cout << "called " << n << ' ' << divisor << '\n';
    if(n == 1){
        // for(auto j: now) cout << j << ' ';
        // cout << '\n';
        calculate();
        return;
    }
    vector<int> divisors;
    for(int i = 1; i <= sqrt(n); ++i){
        if(n % i == 0){
            if(i * i == n) divisors.push_back(i);
            else{
                divisors.push_back(i);
                divisors.push_back(n / i);
            }
        }
    }
    sort(divisors.begin(), divisors.end());
    // for(auto i: divisors) cout << i << ' ';
    // cout << '\n';
    for(auto i = divisors.begin(); i != divisors.end(); ++i){
        if(*i < divisor) continue;
        now.push_back(*i);
        dfs(n / *i, *i);
        now.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    dfs(n, 2);
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto i: ans){
        cout << i << ' ';
    }
}

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