Submission #881837

#	Time	Username	Problem	Language	Result	Execution time	Memory
881837		Sharky	Toys (CEOI18_toy)	C++17	100 / 100	447 ms	29004 KiB

toy

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

struct Hash {
    size_t operator () (const pair<int,int> &x) const {
        return hash<long long>()(((long long) x.first) ^ (((long long) x.second) << 32));
    }
};

vector<int> can;
unordered_map<pair<int, int>, bool, Hash> mp;

void dfs(int u, int lst, int sum) {
    // cout << u << " " << lst << " " << sum << '\n';
    if (mp.count({u, sum})) return;
    mp[{u, sum}] = 1;
    if (u == 1) {
        can.push_back(sum);
        return;
    }
    for (int i = lst; i * i <= u; i++) {
        if (u % (i + 1) == 0) dfs(u / (i + 1), i, sum + i);
    }
    dfs(1, u, sum + u - 1);
}

int32_t main() {
    int n;
    cin >> n;
    dfs(n, 1, 0);
    sort(can.begin(), can.end());
    cout << can.size() << '\n';
    for (auto& u : can) cout << u << ' ';
    cout << '\n';
}

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