Submission #217862

#	Time	Username	Problem	Language	Result	Execution time	Memory
217862		DystoriaX	Toys (CEOI18_toy)	C++14	100 / 100	4255 ms	17176 KiB

toy

#include <bits/stdc++.h>

using namespace std;

int n;
int cnt[21];
vector<int> p, ans;
int sum = 0;

void check(int x){
    for(int i = 2; 1LL * i * i <= x; i++){
        if(x % i == 0){
            p.emplace_back(i);

            while(x % i == 0) x /= i, cnt[p.size() - 1]++;
        }
    }

    if(x > 1) p.emplace_back(x), cnt[p.size() - 1]++;
}

int t = 0;

void brute(int pre, int cur, int idx){
    bool sub = false;
    if(idx == (int) p.size()){
        if(pre > cur) return;

        sum += cur - 1;

        idx = 0, pre = cur, cur = 1;
        sub = true;
        
        if(n == 1){
            ans.emplace_back(sum);
            sum -= pre - 1;

            return;
        }
    }

    int prod = 1, res = cnt[idx];

    if(cnt[idx] == 0){
        brute(pre, cur, idx + 1);
    } else {
        // int tmp = t++;
        // cout << tmp << ": " << pre << " " << cur << " " << idx << " " << cnt[idx] << endl;
        // cout << pr << endl;

        for(int i = 0; i <= res; i++){
            if(i) n /= p[idx], prod *= p[idx], cnt[idx]--;

            brute(pre, cur * prod, idx + 1);
        }

        cnt[idx] = res;
        n *= prod;

        // cout << tmp << ": " << pre << " " << cur << " " << idx << " " << cnt[idx] << endl;
    }

    if(sub){
        sum -= pre - 1;
    }
}

int main(){
    scanf("%d", &n);

    check(n);

    brute(2, 1, 0);

    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    if(n == 1) ans.emplace_back(0);

    printf("%d\n", (int) ans.size());
    for(auto k : ans) printf("%d ", k);
    printf("\n");
    
    return 0;
}

Compilation message (stderr)

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

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