Submission #668684

#	Time	Username	Problem	Language	Result	Execution time	Memory
668684		kinope	Toys (CEOI18_toy)	C++14	59 / 100	5049 ms	19384 KiB

toy

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct st{
	int d, i;
	st(){}
	st(int d) : d(d), i(1) {}
};
void getd(int n, vector<st> &d){
		for(int i = 2; i*i <= n; ++i){
				while(n%i==0){
						if(d.size() && d.back().d == i) ++d.back().i;
						else d.emplace_back(st(i));
						n /= i;
				}
		}
		if(n) d.emplace_back(st(n));
}

int main(){
		int n;
		scanf("%d", &n);
		if(n==1){printf("1\n0");return 0;}
		vector<st> d; getd(n, d);
		set<int> s, tmp; s.emplace(1);
		
		for(st dz : d){
				for(int i : s){
						int w = 1;
						for(int c = 1; c <= dz.i; ++c) w *= dz.d, tmp.emplace(i*w);
						tmp.emplace(i);
				}
				s = tmp; tmp.clear();
		} vector<int> D; for(int i : s) if(i!=1) D.emplace_back(i);
		unordered_map<ll, bool> czy; for(int i : D){czy[i] = 1; }//printf("%d ", i);}
		unordered_map<int, set<int>> dp;
		for(int i : D) dp[i].emplace(i-1);
		for(int i = 0; i < (int) D.size(); ++i){
				int a = D[i];
				//printf("%d ", a);
				for(int w : dp[a]) for(int j = 0; j < (int) D.size(); ++j){
						int b = D[j];
						if(czy[(ll) a * b]) dp[a*b].emplace(w+b-1);
				}
		}
		
		printf("%d\n", (int) dp[n].size());
		for(int i : dp[n]) printf("%d ", i);
		
		return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~

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