Submission #1128735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128735		Alihan_8	Toys (CEOI18_toy)	C++20	39 / 100	5091 ms	107056 KiB

toy

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector <vector<int>> D(N);

signed main(){
	for ( int i = 2; i < N; i++ ){
		for ( int j = i; j < N; j += i ) D[j].push_back(i);
	}
	
	int n; cin >> n;
	
	if ( n == 1 ) return cout << "1\n0\n", 0;
	
	vector <int> d{n};
	
	for ( int i = 2; i * i <= n; i++ ){
		if ( n % i == 0 ){
			d.push_back(i);
			
			if ( i * i != n ) d.push_back(n / i);
		}
	}
	
	sort(d.begin(), d.end());
	
	vector <map<int,bool>> mp(n);
	
	auto dfs = [&](auto dfs, int s, int x) -> bool{
		if ( s == 0 && x == 1 ) return true;
		
		if ( mp[s].count(x) ) return mp[s][x];
		
		bool &ret = mp[s][x]; ret = 0;
		
		for ( auto &y: D[x] ){
			if ( y > s + 1 ) break;
			
			ret |= dfs(dfs, s + 1 - y, x / y);
		}
		
		return ret;
	};
	
	vector <int> ans;
	
	for ( int i = 1; i < n; i++ ){
		if ( dfs(dfs, i, n) ) ans.push_back(i);
	}
	
	cout << ans.size() << '\n';
	
	for ( auto &x: ans ) cout << x << ' ';
	
	cout << '\n';
}

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