oj.uz

Submission #73487

# Submission time Handle Problem Language Result Execution time Memory
73487 2018-08-28T10:29:30 Z duckmoon99 Toys (CEOI18_toy) C++14
0 / 100
 3 ms 676 KB 
#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[divi[n/i]].empty())solve(divi[n/i]);
			for(auto it: dp[divi[i]]){
				for(auto itt: dp[divi[n/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

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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Runtime error 3 ms 676 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Runtime error 3 ms 676 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Runtime error 3 ms 676 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Runtime error 3 ms 676 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Runtime error 3 ms 676 KB Execution killed with signal 8 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -