| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 749690 |
2023-05-28T11:39:20 Z |
finn__ |
Teams (CEOI11_tea) |
C++17 |
|
2500 ms |
44564 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);
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:57:1: warning: control reaches end of non-void function [-Wreturn-type]
57 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 2 |
Correct |
16 ms |
16708 KB |
Output is correct |
| 3 |
Incorrect |
19 ms |
16716 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
16760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
16648 KB |
Output is correct |
| 2 |
Correct |
25 ms |
16752 KB |
Output is correct |
| 3 |
Correct |
22 ms |
16724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
16832 KB |
Output is correct |
| 2 |
Correct |
44 ms |
16812 KB |
Output is correct |
| 3 |
Correct |
43 ms |
16824 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
16844 KB |
Output is correct |
| 2 |
Incorrect |
38 ms |
16824 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
206 ms |
18748 KB |
Output is correct |
| 2 |
Correct |
241 ms |
18420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
274 ms |
18920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2490 ms |
34520 KB |
Output is correct |
| 2 |
Correct |
2125 ms |
33028 KB |
Output is correct |
| 3 |
Correct |
2308 ms |
35264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2574 ms |
33964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1909 ms |
44564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
