oj.uz

Submission #217861

# Submission time Handle Problem Language Result Execution time Memory
217861 2020-03-31T04:56:23 Z DystoriaX Toys (CEOI18_toy) C++14
0 / 100
 5 ms 256 KB 
#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());

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

    printf("\n");
    
    return 0;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -