Submission #73489

#	Time	Username	Problem	Language	Result	Execution time	Memory
73489		duckmoon99	Toys (CEOI18_toy)	C++14	79 / 100	5086 ms	52404 KiB

toy

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

vi divi;
unordered_map <int, unordered_set<int> > dp;

void solve(int n){
	dp[n].insert(n-1);
	for(int i = 0; i < divi.size() && divi[i]<=sqrt(n); i++){
		if(n%divi[i]==0){
			if(dp[divi[i]].empty())solve(divi[i]);
			if(dp[n/divi[i]].empty())solve(n/divi[i]);
			for(auto it: dp[divi[i]]){
				for(auto itt: dp[n/divi[i]]){
					dp[n].insert(it+itt);
				}
			}
		}
	}
}

vi ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	dp.max_load_factor(0.25);dp.reserve(512);
	if(n==1){
		cout << 1 << '\n' << 0;
		ret 0;
	}
	for(int i = 2; i <= sqrt(n); i++){
		if(n%i==0){
			divi.pb(i);
			if(n/i != i){
				divi.pb(n/i);
			}
		}
	}
	sort(divi.begin(),divi.end());
	solve(n);
	cout << dp[n].size() << endl;
	for(auto it: dp[n]){
		ans.pb(it);
	}
	sort(ans.begin(),ans.end());
	n = ans.size();
	for(int i = 0; i < n; i++){
		cout << ans[i] << " ";
	}
}

Compilation message (stderr)

toy.cpp: In function 'void solve(int)':
toy.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < divi.size() && divi[i]<=sqrt(n); i++){
                 ~~^~~~~~~~~~~~~

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