Submission #425528

#	Time	Username	Problem	Language	Result	Execution time	Memory
425528		Runtime_error_	Toys (CEOI18_toy)	C++14	100 / 100	2228 ms	4816 KiB

toy

#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;
vector<int> ls;

void bt(int Divisor,int SumBefore,int curnum,bool larger,int SumAll){

    if(SumAll == 0 && Divisor == 0){
        if(mp.find(SumBefore) == mp.end())
            ans.pb(SumBefore),mp[SumBefore];
        return ;
    }
    for(int i=(larger?0:ls[Divisor]);i<=pf[Divisor].second;i++){
        int tmp = ls[Divisor];
        ls[Divisor] = i;
        curnum*= power[Divisor][i];
        pf[Divisor].second -= i;
        if(Divisor+1 == pf.size() && curnum>1)
                bt(0,SumBefore+curnum-1,1,0,SumAll-i);
        else if(Divisor < pf.size()-1)
            bt(Divisor+1,SumBefore,curnum,larger |(i>tmp ) ,SumAll-i);
        curnum /= power[Divisor][i];
        ls[Divisor] = tmp;
        pf[Divisor].second += i;
    }
}

signed main(){

    scanf("%d",&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 );
    }
    sort(pf.begin(),pf.end());
    int SumAll = 0;
    for(auto o:pf)
        SumAll += o.second;
//    for(auto o:pf)
//        cout<<o.first<<" "<<o.second<<endl;
    ls.resize(pf.size(),0);
    bt(0,0,1,0,SumAll);
    sort(ans.begin(),ans.end());

    printf("%d\n",(int)ans.size());
    for(auto o:ans)
        printf("%d\n",o);
}

Compilation message (stderr)

toy.cpp: In function 'void bt(int, int, int, bool, int)':
toy.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         if(Divisor+1 == pf.size() && curnum>1)
      |            ~~~~~~~~~~^~~~~~~~~~~~
toy.cpp:26:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         else if(Divisor < pf.size()-1)
      |                 ~~~~~~~~^~~~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

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