Submission #1032024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032024		NValchanov	Toys (CEOI18_toy)	C++17	100 / 100	2870 ms	117072 KiB

toy

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const ll MAXN = 1e9 + 10;
const int SQRT = 4e4 + 10;

map < ll, bool > dp[SQRT];

ll n, m;
vector < ll > divs;

void read()
{
    cin >> n;

    if(n == 1)
    {
        cout << 1 << endl;
        cout << 0 << endl;
        exit(0);
    }
}

void fill_divs()
{
    for(ll i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            divs.push_back(i);
            if(i * i != n)
                divs.push_back(n / i);
        }
    }
    divs.push_back(1);
    divs.push_back(n);
    m = divs.size();

    sort(divs.begin(), divs.end());
}

void solve()
{
    dp[0][0] = true;

    for(int i = 0; i < m; i++)
    {
        for(int j = i + 1; j < m; j++)
        {
            if(divs[j] % divs[i] == 0)
            {
                int whole = divs[j] / divs[i];

                for(auto it : dp[i])
                {
                    dp[j][it.first + whole - 1] = true;
                }
            }
        }
    }
}

void print()
{
    cout << dp[m - 1].size() << endl;
    for(auto it : dp[m - 1])
    {
        cout << it.first << " ";
    }
    cout << endl;
}

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

    read();
    fill_divs();
    solve();
    print();

    return 0;
}

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