oj.uz

Submission #424992

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

#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(ans.count(SumBefore))
                assert(0);
            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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -