Submission #72621

#	Time	Username	Problem	Language	Result	Execution time	Memory
72621		istlemin	Toys (CEOI18_toy)	C++14	59 / 100	5037 ms	56572 KiB

toy

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define re(i,a,b) for(i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

map<ll,ll> getFactors(ll x){
	map<ll,ll> res;
    rep(i,2,sqrt(x)+1){
		//cout<<i<<" "<<x<<endl;
        if(x%i==0){
			x/=i;
			res[i]++;
			i = 1;
        }
    }
    res[x]++;
    return res;
}

set<ll> ans;
map<pair<vi,ll>,bool> seen;
vi f;

void getAns(vi facs,ll sum){
    if(seen[{facs,sum}]) return;
    seen[{facs,sum}] = true;
    bool all0 = true;
	rep(i,0,facs.size()) {
		all0 &= (facs[i]==0);
        //cout<<facs[i]<<" ";
	}
	//cout<<endl;
	//cout<<sum<<": "<<endl;
	if(all0){
		ans.insert(sum);
		return;
	}

    vi l(facs.size());
    re(l[0],0,facs[0]+1)
    re(l[1],0,facs[1]+1)
    re(l[2],0,facs[2]+1)
    re(l[3],0,facs[3]+1)
    re(l[4],0,facs[4]+1)
    re(l[5],0,facs[5]+1)
    re(l[6],0,facs[6]+1)
    re(l[7],0,facs[7]+1)
    re(l[8],0,facs[8]+1)
    re(l[9],0,facs[9]+1)
    re(l[10],0,facs[10]+1)
    re(l[11],0,facs[11]+1){
        ll add = 1;
        rep(i,0,facs.size()) add *= pow(f[i],facs[i]-l[i]);
        getAns(l,sum+add-1);
    }
}

int main(){
	cin.sync_with_stdio(false);
	ll n;
	cin>>n;

    vi facs;
    trav(fi,getFactors(n)){
        facs.push_back(fi.second);
        f.push_back(fi.first);
        //cout<<f.first<<" "<<f.second<<endl;
    }
    //cout<<endl;

    while(facs.size()<12) {
		facs.push_back(0);
		f.push_back(1);
	}
    getAns(facs,0);
    cout<<ans.size()<<endl;
    trav(a,ans){
		cout<<a<<" ";
    }
    cout<<endl;
}

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