Submission #696864

#	Time	Username	Problem	Language	Result	Execution time	Memory
696864		Johann	Teams (CEOI11_tea)	C++14	100 / 100	322 ms	94436 KiB

tea

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

typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vpii A(n);
    for (int i = 0; i < n; ++i)
        cin >> A[i].first, A[i].second = i + 1;

    sort(all(A), greater<pii>());

    vvi con(n);
    for (int j = 0, i; j < n - 1; ++j)
    {
        i = j + A[j + 1].first;
        if (i < n)
            con[i].push_back(j);
    }

    vi last(n, -1);
    vi TeamsR(n, 0);
    vi MaxTeamsR(n, 0);
    vi lastMaxIdx(n, 0);
    for (int i = 0; i < A[0].first; ++i)
        TeamsR[i] = INT_MIN, MaxTeamsR[i] = 0;
    TeamsR[A[0].first - 1] = 1, MaxTeamsR[A[0].first - 1] = A[0].first;

    for (int i = A[0].first; i < n; ++i)
    {
        // expand the last team
        TeamsR[i] = TeamsR[i - 1];
        last[i] = last[i - 1];
        MaxTeamsR[i] = MaxTeamsR[i - 1];
        if (MaxTeamsR[i] < i - last[i])
        {
            if (TeamsR[i] * MaxTeamsR[i] >= i + 1)
                last[i] = last[i] + 1;
            else
                MaxTeamsR[i] = i - last[i];
        }
        // create new team
        for (int j : con[i])
        {
            int tmp = TeamsR[j] + 1;
            int len = max(MaxTeamsR[j], i - j);
            if ((tmp > TeamsR[i]) || (tmp == TeamsR[i] && MaxTeamsR[i] > len) || (tmp == TeamsR[i] && MaxTeamsR[i] == len && last[i] < j))
            {
                TeamsR[i] = tmp;
                MaxTeamsR[i] = len;
                last[i] = j;
            }
        }
    }

    // cout << TeamsR.back() << "\n";

    vi order;
    int idx = n - 1;
    while (idx >= 0)
    {
        order.push_back(idx);
        idx = last[idx];
    }
    reverse(all(order));
    cout << sz(order) << "\n";
    idx = 0;
    for (int x : order)
    {
        cout << x - idx + 1 << " ";
        while (idx <= x)
            cout << A[idx++].second << " ";
        cout << "\n";
    }
    cout << "\n";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10