oj.uz

Submission #425020

# Submission time Handle Problem Language Result Execution time Memory
425020 2021-06-12T12:30:57 Z Runtime_error_ Toys (CEOI18_toy) C++14
0 / 100
 1 ms 332 KB 

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

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(mp.find(SumBefore) == mp.end())
            ans.pb(SumBefore),mp[SumBefore];
    }
    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,0);
        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(int i=2;i<=n/i;i++){
        int cnt = 0;
        while( (n%i) == 0)
            cnt++,n/=i;
        if(cnt > 0){
            pf.pb(pi(i,cnt));
            power[ pf.size()-1 ].pb(1);
            for(int 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(int 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);
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<endl;
    for(auto o:ans)
        cout<<o<<endl;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -