Submission #142895

#	Time	Username	Problem	Language	Result	Execution time	Memory
142895		shayan_p	Toys (CEOI18_toy)	C++14	100 / 100	1126 ms	20188 KiB

toy

// only miss the sun when it starts to snow

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e5+10,mod=1e9+7;
const ll inf=1e18;

vector<int>vec, v[maxn], ans;
unordered_map<int,int> mp;

void solve(int id,int sm,int lim){
    if(id==0){
	ans.PB(sm);
	return;
    }
    for(int x:v[id]){
	if(x==1) continue;
	if(x>lim) break;
	solve( mp[ vec[id] / x ], sm + x -1, x);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n; cin>>n;

    if(n==1) return cout<<1<<"\n"<<0<<endl,0;
    
    for(int i=1;i*i<=n;i++){
	if(n%i==0) vec.PB(i);
    }
    for(int i=sz(vec)-1;i>=0;i--){
	if(vec[i]*vec[i]!=n) vec.PB(n/vec[i]);
    }
    for(int i=0;i<sz(vec);i++){
	mp[vec[i]]=i;
    }
    
    for(int i=0;i<sz(vec);i++){
	for(int j=0;j<=i;j++)
	    if(vec[i] % vec[j] == 0) v[i].PB(vec[j]);
    }
    solve(sz(vec)-1,0,n);
    sort(ans.begin(), ans.end());
    ans.resize( unique(ans.begin(), ans.end()) - ans.begin() );
    cout<<sz(ans)<<"\n";
    for(int x:ans)
	cout<<x<<" ";
    return cout<<endl,0;
}
// Deathly mistakes:
//  * Read the problem carefully.
//  * Check maxn.
//  * Overflows.


// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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