Submission #825917

#	Time	Username	Problem	Language	Result	Execution time	Memory
825917		sentheta	Toys (CEOI18_toy)	C++17	100 / 100	1438 ms	16960 KiB

toy

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

// #define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}










int n;

V<int> s;

void bf(int x=n,int lim=n,int sum=0){
	if(x==1){
		s.push_back(sum);
		// s.insert(sum);
		return;
	}
	
	for(int y=1; y*y<=x; y++) if(x%y==0){
		int z = x/y;
		
		if(y>1 && y<=lim){
			bf(z, y, sum+y-1);
		}
		if(z>1 && z<=lim && y!=z){
			bf(y, z, sum+z-1);
		}
	}
}

void solve(){
	
	cin >> n;
	
	bf();
	
	sort(all(s));
	int uniq = 1;
	rep(i,1,s.size()){
		uniq += s[i]!=s[i-1];
	}
	
	cout << uniq << nl;
	cout << s[0] << " ";
	rep(i,1,s.size()){
		if(s[i]!=s[i-1]) cout << s[i] << " ";
	}
	
	// cout << s.size() << nl;
	// for(int x : s) cout << x << " ";
	// cout << nl;
	
	
	
	
	
}

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