Submission #424824

#	Time	Username	Problem	Language	Result	Execution time	Memory
424824		Runtime_error_	Toys (CEOI18_toy)	C++14	0 / 100	1 ms	204 KiB

toy

/*
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 109,MX = 15000,mod = 1e9+7;
ll fib[inf],n,m,a[inf],dp[inf][MX];

ll solve(ll i,ll rem){
    if(rem < 0)return 0;
    if(i == m+1)
        return rem == 0;
    ll &ret  = dp[i][rem];
    if(ret != -1)
        return ret;
    ret = (solve(i+1,rem) + solve(i+1,rem-fib[i]))%mod;
    return ret;
}

signed main()
{

    fib[1] = 1;
    fib[2] = 2;
    for(m=3;m<inf;m++){
        fib[m] = fib[m-1]+fib[m-2];
    }
    memset(dp,-1,sizeof(dp));
   cin>>n;
    for(ll i=1;i<=n;i++)
        cin>>a[i],a[i] = fib[a[i]]+a[i-1],cout<<solve(1,a[i])<<endl;
}
*/

#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){
        if(larger)
            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;
    for(auto o:pf)
        ls.pb(0);
    bt(ls,{},0,1,0);

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

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:95:14: warning: variable 'o' set but not used [-Wunused-but-set-variable]
   95 |     for(auto o:pf)
      |              ^

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