Submission #1223942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223942		LeonidCuk	Toys (CEOI18_toy)	C++20	100 / 100	1314 ms	86616 KiB

toy

#include <bits/stdc++.h>
using namespace std;
vector<long long int>fact;
vector<set<int>>dp;
void vrni(int a,vector<pair<int,int>>&v,int l)
{
    fact.push_back(a);
    if(a==1)return;
    for(int i=l;i<v.size();i++)
    {
        if(v[i].second!=0)
        {
            v[i].second--;
            vrni(a/v[i].first,v,i);
            v[i].second++;
        }
    }
}
void vmerge(int k,int a,int b)
{
    for(auto it=dp[a].begin();it!=dp[a].end();it++)
    {
            dp[k].insert(*it+b-1);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    map<int,int>m;
    int n,k;
    cin>>n;
    k=n;
    vector<pair<int,int>>v;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)v.push_back({i,0});
        while(n%i==0)
        {
            n=n/i;
            (v.back()).second++;
        }
    }
    if(n!=1)v.push_back({n,1});
    vrni(k,v,0);
    sort(fact.begin(),fact.end());
    for(int i=0;i<fact.size();i++)m[fact[i]]=i;
    dp.resize(fact.size());
    for(int i=0;i<fact.size();i++)
    {
        dp[i].insert(fact[i]-1);
        for(int j=i-1;j>=0;j--)
        {
            if(fact[i]*fact[i]<fact[j])continue;
            if(fact[i]%fact[j]==0)
            {
                vmerge(i,j,fact[i]/fact[j]);
            }
        }
    }
    cout<<dp[dp.size()-1].size()<<endl;
    for(auto it=dp[dp.size()-1].begin();it!=dp[dp.size()-1].end();it++)
    {
        cout<<*it<<" ";
    }
}

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