Submission #490981

#	Time	Username	Problem	Language	Result	Execution time	Memory
490981		hollwo_pelw	Toys (CEOI18_toy)	C++17	100 / 100	3584 ms	17092 KiB

toy

#include <bits/stdc++.h>
using namespace std;

vector<int> d, res;

void backtrack(int val, int cur, int sum = 0) {
    if (val == 1)
        return res.push_back(sum), (void) 0;
    if (cur == d.size()) return ;
    
    int x = d[cur];
    
    if (val < x) return ;
    if (val == x)
        return backtrack(val / x, cur + 1, sum + x - 1);
    
    backtrack(val, cur + 1, sum);
    while (val % x == 0) {
        val /= x, sum += x - 1;
        backtrack(val, cur + 1, sum);
    }
}

signed main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int n; cin >> n;
	for (int i = 2; i * i <= n; i++) {
	    if (n % i == 0) {
	        d.push_back(i);
	        if (n / i != i)
	            d.push_back(n / i);
	    }
	}
	sort(d.begin(), d.end());
	
	backtrack(n, 0);
	
	res.push_back(n - 1);
	sort(res.begin(), res.end());
	res.erase(unique(res.begin(), res.end()), res.end());
	
	cout << res.size() << '\n';
	for (auto v : res)
	    cout << v << ' ';
}

Compilation message (stderr)

toy.cpp: In function 'void backtrack(int, int, int)':
toy.cpp:9:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     if (cur == d.size()) return ;
      |         ~~~~^~~~~~~~~~~

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