oj.uz

답안 #749696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749696 2023-05-28T11:42:23 Z finn__ Teams (CEOI11_tea) C++17
80 / 100
 2500 ms 43272 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 1000001, L = 1 << 20;

size_t n;
pair<int, int> a[N];
int tree[2 * L][2], pre[N];

void update(size_t i, int x, int y)
{
    i += L;
    tree[i][0] = x;
    tree[i][1] = y;
    while (i >>= 1)
    {
        tree[i][0] = max(tree[i << 1][0], tree[(i << 1) | 1][0]);
        tree[i][1] = tree[i << 1][0] > tree[(i << 1) | 1][0] ? tree[i << 1][1] : tree[(i << 1) | 1][1];
    }
}

pair<int, int> range_max(size_t i, size_t j)
{
    i += L, j += L;
    int x = 0, y = 0;
    while (i <= j)
    {
        if (i & 1)
        {
            y = tree[i][0] > x ? tree[i][1] : y;
            x = max(x, tree[i++][0]);
        }
        if (!(j & 1))
        {
            y = tree[j][0] > x ? tree[j][1] : y;
            x = max(x, tree[j--][0]);
        }
        i >>= 1;
        j >>= 1;
    }
    return {x, y};
}

int max_number_of_teams(size_t max_team_size)
{
    memset(tree, 0, sizeof tree);
    for (size_t i = 1; i <= n; ++i)
        if (i >= a[i].first)
        {
            size_t u = i - min(max_team_size, i), v = i - a[i].first;
            auto const [x, y] = range_max(u, v);
            if (u && !x)
            {
                if (i == n)
                    return 0;
                continue;
            }
            pre[i] = y;
            if (i == n)
                return x + 1;
            update(i, x + 1, i);
        }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (size_t i = 1; i <= n; ++i)
        cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + n + 1);

    int t = max_number_of_teams(n);
    cout << t << '\n';
    size_t u = a[n].first, v = n;
    while (u < v)
    {
        size_t mid = (u + v) / 2;
        if (max_number_of_teams(mid) == t)
            v = mid;
        else
            u = mid + 1;
    }

    assert(max_number_of_teams(u) == t);
    int i = n;
    while (i)
    {
        vector<int> team;
        for (int j = pre[i] + 1; j <= i; ++j)
            team.push_back(a[j].second);
        i = pre[i];
        cout << team.size() << ' ';
        for (int const &x : team)
            cout << x << ' ';
        cout << '\n';
    }
}

Compilation message

tea.cpp: In function 'int max_number_of_teams(size_t)':
tea.cpp:48:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if (i >= a[i].first)
      |             ~~^~~~~~~~~~~~~
tea.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 18 ms 16724 KB Output is correct
3 Correct 16 ms 16724 KB Output is correct
4 Correct 17 ms 16716 KB Output is correct
5 Correct 17 ms 16672 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 16744 KB Output is correct
2 Correct 21 ms 16724 KB Output is correct
3 Correct 20 ms 16724 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 16724 KB Output is correct
2 Correct 25 ms 16752 KB Output is correct
3 Correct 21 ms 16724 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 16804 KB Output is correct
2 Correct 45 ms 16792 KB Output is correct
3 Correct 41 ms 16792 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 18280 KB Output is correct
2 Correct 231 ms 18068 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 18408 KB Output is correct
2 Correct 216 ms 18224 KB Output is correct
3 Correct 258 ms 18896 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2458 ms 30636 KB Output is correct
2 Correct 2129 ms 30760 KB Output is correct
3 Correct 2201 ms 31172 KB Output is correct

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2559 ms 28168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1374 ms 37744 KB Output is correct
2 Correct 190 ms 43272 KB Output is correct
3 Execution timed out 2562 ms 32268 KB Time limit exceeded
4 Halted 0 ms 0 KB -