Submission #255691

#	Time	Username	Problem	Language	Result	Execution time	Memory
255691		cfalas	Toys (CEOI18_toy)	C++14	100 / 100	4019 ms	86928 KiB

toy

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID (l+r)/2
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
//typedef cc_hash_table<int, set<int>, hash<set<int> >> ht;
//map<int, set<int>> ans;
unordered_map<int, set<int> > ans;
int cnt=0;
int desc(ll n, set<int> cdiv=set<int>()){
    if(ans.count(n)!=0) return ans[n].size();
	//cout<<cdiv.size()<<endl;
	if(cdiv.empty()){
		cnt++;
		for(int i=2;i*i<=n;i++){
			if(n%i==0) cdiv.insert(i);
		}
	}
	else{
		auto i = cdiv.begin();
		while(i!=cdiv.end()){
			//cout<<n<<" "<<*i<<endl;
			if(*(i)==0 || n%(*(i))!=0 || n==*i) i = cdiv.erase(i);
			else i++;
		}
		//cout<<"-----"<<endl;

	}
	for(auto i : cdiv){
        if(n%i) continue;
        desc(n/i, cdiv);
		for(auto q : ans[n/i])
			ans[n].insert(q+i-1);
    }
    ans[n].insert(n-1);
    return ans[n].size();
}

int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    ll n;
    cin>>n;
    cout<<desc(n)<<endl;
    //for(int i=1;i<=10;i++) cout<<desc(i)<<" ";
    for(auto v : ans[n]) cout<<v<<" ";
	assert(cnt==1);
}

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