Submission #920778

#	Time	Username	Problem	Language	Result	Execution time	Memory
920778		Ghulam_Junaid	Toys (CEOI18_toy)	C++17	79 / 100	2065 ms	262144 KiB

toy

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

const int N = 3005;

int n, ite;
vector<int> store[N];
unordered_map<int, int> id;
vector<int> divs, imp[N];

inline void F(int x){
    store[id[x]].push_back(x - 1);
    for (int d : imp[id[x]]){
        for (int a : store[id[d]])
            for (int b : store[id[x]])
                store[id[d * x]].push_back(a + b);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    int cpy = n;

    for (int x = 2; x * x <= n; x ++){
        if (n % x) continue;
        divs.push_back(x);
        if (x * x != n)
            divs.push_back(n / x);
    }
    divs.push_back(n);

    sort(divs.begin(), divs.end());  
    for (int i = 0; i < divs.size(); i ++){
        id[divs[i]] = i;
        for (int j = 0; j <= i; j ++){
            long long prod = 1ll * divs[i] * divs[j];
            if (prod > n)
                break;
            if (n % prod == 0)
                imp[id[divs[i]]].push_back(divs[j]);
        }
    }

    for (int x : divs){
        sort(store[id[x]].begin(), store[id[x]].end());
        store[id[x]].resize(unique(store[id[x]].begin(), store[id[x]].end()) - store[id[x]].begin());
        F(x);
    }

    if (n == 1) store[id[n]] = {0};
    vector<int> output = store[id[n]];
    cout << output.size() << endl;
    for (int x : output)
        cout << x << " ";
    cout << '\n';
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < divs.size(); i ++){
      |                     ~~^~~~~~~~~~~~~
toy.cpp:25:9: warning: unused variable 'cpy' [-Wunused-variable]
   25 |     int cpy = n;
      |         ^~~

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