Submission #1243368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243368		DangKhoizzzz	Toys (CEOI18_toy)	C++17	79 / 100	2552 ms	327680 KiB

toy

/*
8 6 5
hi welcome hello ihateyou goaway dog cat rat
1 hi welcome
1 ihateyou goaway
2 hello ihateyou
2 hi goaway
2 hi hello
1 hi hello
dog cat
dog hi
hi hello
ihateyou goaway
welcome ihateyou
*/

#include <bits/stdc++.h>
#define pii pair <int , int>
#define fi first
#define se second
#define pii pair <int , int> 


using namespace std;

const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;

int n;
vector <short> g[maxn];
vector <int> dp[maxn];
vector <int> uoc;

void build ()
{
    for(int i = 1; i <= n; i++)
    {
        if(n%i == 0)
        {
            uoc.push_back(i);
            if(n/i != i) uoc.push_back(n/i);
        }
    }
    sort(uoc.begin() , uoc.end());
    for(int i = 0; i < uoc.size(); i++)
    {
        for(int j = i+1; j < uoc.size(); j++)
        {
            if(uoc[j] % uoc[i] == 0) g[i].push_back(j);
        }
    }
}

void solve()
{
    cin >> n;
    build();
    dp[0] = {0};

    for(int i = 0; i < uoc.size(); i++)
    {
        sort(dp[i].begin() , dp[i].end());
        dp[i].erase(unique(dp[i].begin() , dp[i].end()) , dp[i].end());
        for(int j: g[i])
        {
            for(int x: dp[i])
            {
                dp[j].push_back(x + (uoc[j]/uoc[i] - 1));
            }
        }
    }
    cout << dp[-1 + (int)uoc.size()].size() << '\n';
    for(int x: dp[-1 + (int)uoc.size()]) cout << x << ' ';
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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