Submission #114789

#	Time	Username	Problem	Language	Result	Execution time	Memory
114789		Meloric	Toys (CEOI18_toy)	C++14	100 / 100	1313 ms	83456 KiB

toy

#include <bits/stdc++.h>
#define int int64_t
#define pb push_back
#define X first
#define Y second
#define pii pair<int, int>

using namespace std;

unordered_map<int, unordered_set<int>> mem;

vector<int> divs(int n){
    vector<int> ans;
    for(int i = 1; i*i<=n; i++){
        if(n%i == 0){
            ans.pb(i);
            ans.pb(n/i);
        }
    }
    return ans;
}
void dp(int n){
    if(mem.find(n)!= mem.end())return;
    vector<int> dv;
    dv = divs(n);
    unordered_set<int> ans;
    for(int i = 1; i< dv.size(); i++){
        int tmp = n/dv[i];
        dp(tmp);
        for(int j : mem.find(tmp)->Y){
            ans.insert(j+dv[i]-1);
        }
    }
    mem.insert({n, ans});
}
signed main(){
    int n; cin >> n;
    mem.insert({1, {0}});
    dp(n);
    vector<int> ans;
    for(int j : mem.find(n)->Y){
        ans.pb(j);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size()<<'\n';
    for(int j : ans){
        cout << j << ' ';
    }
}

Compilation message (stderr)

toy.cpp: In function 'void dp(int64_t)':
toy.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i< dv.size(); i++){
                    ~^~~~~~~~~~~

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