Submission #1314686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314686		Sam_a17	Gift (IZhO18_nicegift)	C++20	0 / 100	221 ms	51656 KiB

nicegift

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

const int N = 1e6 + 10;

int n, k;
long long a[N];

int comp_num;
deque<pair<long long, int>> components[N / 1000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;

    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
        mx = max(mx, a[i]);
    }

    if (sum % k != 0 || mx > (sum / k))
    {
        cout << -1 << '\n';
        return 0;
    }

    long long needSum = sum / k;

    long long blockSum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (blockSum + a[i] <= needSum)
        {
            blockSum += a[i];
            components[comp_num].push_back(make_pair(a[i], i));
        }
        else
        {
            a[i] -= needSum - blockSum;
            blockSum = needSum;
            i--;
        }

        if (blockSum == needSum)
        {
            comp_num++;
            blockSum = 0;
        }
    }

    vector<vector<long long>> ans;

    while (sum)
    {
        long long min_sum = INT64_MAX;
        for (int i = 0; i < comp_num; ++i)
        {
            assert(components[i].size());
            min_sum = min(min_sum, components[i].front().first);
        }

        vector<long long> seq;
        seq.push_back(min_sum);

        for (int i = 0; i < comp_num; ++i)
        {
            assert(components[i].size());
            seq.push_back(components[i].front().second);
            components[i].front().first -= min_sum;
            if (!components[i].front().first)
            {
                components[i].pop_front();
            }
        }

        sum -= min_sum * comp_num;
        ans.push_back(seq);
    }

    cout << ans.size() << '\n';
    for (auto& i : ans)
    {
        for (auto j : i)
        {
            cout << j << " ";
        }
        cout << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 51