Submission #536852

#	Time	Username	Problem	Language	Result	Execution time	Memory
536852		ecx	Toys (CEOI18_toy)	C++17	100 / 100	1208 ms	152176 KiB

toy

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;

struct chash {
    const uint64_t C = ll(4e18 * acos(0)) | 71;
    ll operator()(ll x) const {
        return __builtin_bswap64(x*C);
    }
};

gp_hash_table<ll, ll, chash> h({}, {}, {}, {}, {1<<16});

bool srch(int n, int k) {
    ll key = ((ll)n)<<32;
    key += k;
    if (h.find(key) == h.end()) {
        h.insert({key,key});
        return false;
    }
    return true;
}

set<int> s;
void dp(int n, int built) {
    if (srch(n, built)) return;
    s.insert(n+built-1);

    for (int i = 2; i*i<=n; i++) {
        if (n%i==0) {
            dp(n/i, built+i-1);
        }
    }
}

int main() {

    int n;
    cin >> n;
    dp(n, 0);
    cout << s.size() << endl;
    for (int k : s) cout << k << " ";
    cout << endl;

}

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