#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 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
8532 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
8532 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
8724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
8660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
113 ms |
10960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
136 ms |
11544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1515 ms |
33804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1850 ms |
42084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1204 ms |
38096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
