제출 #1223920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1223920		LeonidCuk	Toys (CEOI18_toy)	C++20	39 / 100	7 ms	328 KiB

toy

#include <bits/stdc++.h>
using namespace std;
vector<int>fact;
vector<vector<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(int i=0;i<dp[a].size();i++)
    {
        for(int j=0;j<dp[b].size();j++)
        {
            dp[k].push_back(dp[a][i]+dp[b][j]);
        }
    }
    sort(dp[k].begin(),dp[k].end());
    dp[k].erase(unique(dp[k].begin(),dp[k].end()),dp[k].end());
}
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].push_back(fact[i]-1);
        for(int j=i-1;j>=0;j--)
        {
            if(fact[j]*fact[j]<fact[i])break;
            if(fact[i]%fact[j]==0)
            {
                vmerge(i,j,m[fact[i]/fact[j]]);
            }
        }
    }
    cout<<dp[dp.size()-1].size()<<endl;
    for(auto i:dp[dp.size()-1])
    {
        cout<<i<<" ";
    }
}

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