oj.uz

답안 #696864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
696864 2023-02-07T12:59:20 Z Johann Teams (CEOI11_tea) C++14
100 / 100
 322 ms 94436 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 772 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 712 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 6860 KB Output is correct
2 Correct 24 ms 7248 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 8004 KB Output is correct
2 Correct 22 ms 6860 KB Output is correct
3 Correct 31 ms 7876 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 67580 KB Output is correct
2 Correct 217 ms 66592 KB Output is correct
3 Correct 231 ms 66336 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 88544 KB Output is correct
2 Correct 308 ms 94436 KB Output is correct
3 Correct 294 ms 88648 KB Output is correct
4 Correct 281 ms 79052 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 76776 KB Output is correct
2 Correct 196 ms 61976 KB Output is correct
3 Correct 296 ms 89364 KB Output is correct
4 Correct 322 ms 89084 KB Output is correct