Submission #444081

#	Time	Username	Problem	Language	Result	Execution time	Memory
444081		LittleCube	Toys (CEOI18_toy)	C++14	100 / 100	3695 ms	2232 KiB

toy

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

void Merge(vector<int> &big, vector<int> small)
{
    vector<int> ans;
    int idx = 0, jdx = 0;
    for (; idx < big.size() || jdx < small.size();)
    {
        if (idx >= big.size())
            ans.emplace_back(small[jdx++]);
        else if (jdx >= small.size())
            ans.emplace_back(big[idx++]);
        else if (small[jdx] < big[idx])
            ans.emplace_back(small[jdx++]);
        else
            ans.emplace_back(big[idx++]);
    }
    ans.swap(big);
}

vector<int> solve(int N, int K)
{
    vector<int> ans;
    if (N <= K)
        ans = {N - 1};

    for (int i = 2; i <= sqrt(N); i++)
        if (N % i == 0)
        {
            vector<int> v, w;
            if (N / i <= K)
            {
                v = solve(i, N / i);
                for (int &j : v)
                    j += (N / i - 1);

                Merge(ans, v);
                ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
            }
            if (i <= K)
            {
                w = solve(N / i, i);
                for (int &j : w)
                    j += (i - 1);

                Merge(ans, w);
                ans.resize(unique(ans.begin(), ans.end()) - ans.begin());
            }
        }
    return ans;
}

signed main()
{
    int N;
    cin >> N;
    vector<int> ans = solve(N, N);
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " \n"[i == ans.size() - 1];
}

Compilation message (stderr)

toy.cpp: In function 'void Merge(std::vector<int>&, std::vector<int>)':
toy.cpp:9:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (; idx < big.size() || jdx < small.size();)
      |            ~~~~^~~~~~~~~~~~
toy.cpp:9:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (; idx < big.size() || jdx < small.size();)
      |                                ~~~~^~~~~~~~~~~~~~
toy.cpp:11:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         if (idx >= big.size())
      |             ~~~~^~~~~~~~~~~~~
toy.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         else if (jdx >= small.size())
      |                  ~~~~^~~~~~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < ans.size(); i++)
      |                     ~~^~~~~~~~~~~~
toy.cpp:62:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         cout << ans[i] << " \n"[i == ans.size() - 1];
      |                                 ~~^~~~~~~~~~~~~~~~~

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