oj.uz

Submission #749709

# Submission time Handle Problem Language Result Execution time Memory
749709 2023-05-28T11:56:32 Z finn__ Teams (CEOI11_tea) C++17
90 / 100
 2500 ms 49052 KB 
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")

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

template <typename T, size_t L>
struct max_segment_tree
{
    T tree[2 * L];

    void update(size_t i, T x)
    {
        tree[i += L] = x;
        while (i >>= 1)
            tree[i] = max(tree[i << 1], tree[(i << 1) | 1]);
    }

    T range_max(size_t i, size_t j)
    {
        i += L, j += L;
        T x = T();
        while (i <= j)
        {
            if (i & 1)
                x = max(x, tree[i++]);
            if (!(j & 1))
                x = max(x, tree[j--]);
            i >>= 1;
            j >>= 1;
        }
        return x;
    }
};

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

size_t n;
pair<int, int> a[N];
int pre[N];
max_segment_tree<int, L> tree1;
max_segment_tree<pair<int, int>, L> tree2;

int max_number_of_teams(size_t max_team_size)
{
    memset(tree1.tree, 0, sizeof tree1.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;
            int x = tree1.range_max(u, v);
            if (u && !x)
            {
                if (i == n)
                    return 0;
                continue;
            }
            if (i == n)
                return x + 1;
            tree1.update(i, x + 1);
        }
}

void find_predecessor_array(size_t max_team_size)
{
    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 x = tree2.range_max(u, v);
            if (u && !x.first)
                continue;
            pre[i] = x.second;
            tree2.update(i, pair<int, int>(x.first + 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;
    }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8532 KB Output is correct
2 Correct 6 ms 8532 KB Output is correct
3 Correct 6 ms 8532 KB Output is correct
4 Correct 6 ms 8532 KB Output is correct
5 Correct 7 ms 8544 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8532 KB Output is correct
2 Correct 8 ms 8556 KB Output is correct
3 Correct 7 ms 8532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8532 KB Output is correct
2 Correct 12 ms 8576 KB Output is correct
3 Correct 9 ms 8532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8772 KB Output is correct
2 Correct 18 ms 8716 KB Output is correct
3 Correct 18 ms 8712 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8788 KB Output is correct
2 Correct 17 ms 8716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 10592 KB Output is correct
2 Correct 138 ms 11216 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 11208 KB Output is correct
2 Correct 139 ms 11048 KB Output is correct
3 Correct 174 ms 11260 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1588 ms 34116 KB Output is correct
2 Correct 1367 ms 34244 KB Output is correct
3 Correct 1486 ms 31900 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2005 ms 39416 KB Output is correct
2 Correct 1834 ms 47820 KB Output is correct
3 Correct 1849 ms 45820 KB Output is correct
4 Correct 2161 ms 43688 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1084 ms 31092 KB Output is correct
2 Correct 179 ms 27396 KB Output is correct
3 Correct 1914 ms 42848 KB Output is correct
4 Execution timed out 2529 ms 49052 KB Time limit exceeded
5 Halted 0 ms 0 KB -