Submission #424838

#	Time	Username	Problem	Language	Result	Execution time	Memory
424838		Runtime_error_	Toys (CEOI18_toy)	C++14	59 / 100	5037 ms	720 KiB

toy

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pi pair<ll,ll>
using namespace std;
vector<pair<ll,ll> > pf;
ll n;
vector<ll> power[109];
set<ll> ans;

void bt(vector<int> last,vector<int> cur,int SumBefore,int curnum,bool larger){
    bool IsEnd = cur.empty();
    for(auto o:pf)
        if(o.second)
            IsEnd = 0;
    if(IsEnd){

            ans.insert(SumBefore);
        return ;
    }
    int Divisor = cur.size();
    for(int i=(larger?0:last[Divisor]);i<=pf[Divisor].second;i++){
        cur.pb(i);
        curnum*= power[Divisor][i];
        pf[Divisor].second -= i;
        if(cur.size() == pf.size() && curnum>1)
                bt(cur,{},SumBefore+curnum-1,1,larger |(i>last[Divisor] ) );
        else if(cur.size() < pf.size())
            bt(last,cur,SumBefore,curnum,larger |(i>last[Divisor] ) );
        curnum /= power[Divisor][i];
        cur.pop_back();
                pf[Divisor].second += i;

    }
}

signed main(){
    cin>>n;
    for(ll i=2;i*i<=n;i++){
        ll cnt = 0;
        while( (n%i) == 0)
            cnt++,n/=i;
        if(cnt > 0){
            pf.pb(pi(i,cnt));
            power[ pf.size()-1 ].pb(1);
            for(ll j=1;j<=cnt;j++)
                power[ pf.size()-1 ].pb( power[ pf.size()-1 ].back()*i );
        }
    }
    if(n != 1){
            pf.pb(pi(n,1));
            power[ pf.size()-1 ].pb(1);
            for(ll j=1;j<=1;j++)
                power[ pf.size()-1 ].pb( power[ pf.size()-1 ].back()*n );
    }

//    for(auto o:pf)
//        cout<<o.first<<" "<<o.second<<endl;

    vector<int> ls(pf.size(),0);
    bt(ls,{},0,1,0);

    cout<<ans.size()<<endl;
    for(auto o:ans)
        cout<<o<<endl;
}

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