| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 749673 |
2023-05-28T11:15:32 Z |
finn__ |
Teams (CEOI11_tea) |
C++17 |
|
2500 ms |
40016 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], f[N], 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;
if (u > v)
{
f[i] = 0, pre[i] = 0;
continue;
}
auto const [x, y] = range_max(u, v);
f[i] = x + 1, pre[i] = y;
update(i, x + 1, i);
}
return f[n];
}
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 = 1, v = n;
while (u < v)
{
size_t mid = (u + v) / 2;
if (max_number_of_teams(mid) == t)
v = mid;
else
u = mid + 1;
}
max_number_of_teams(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 &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)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16760 KB |
Output is correct |
| 3 |
Incorrect |
17 ms |
16724 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
16648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
16768 KB |
Output is correct |
| 2 |
Correct |
22 ms |
16772 KB |
Output is correct |
| 3 |
Correct |
22 ms |
16724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
16844 KB |
Output is correct |
| 2 |
Correct |
37 ms |
16800 KB |
Output is correct |
| 3 |
Correct |
40 ms |
16832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
16832 KB |
Output is correct |
| 2 |
Incorrect |
39 ms |
16840 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
18540 KB |
Output is correct |
| 2 |
Correct |
232 ms |
18472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
253 ms |
18724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2349 ms |
33560 KB |
Output is correct |
| 2 |
Correct |
2120 ms |
33600 KB |
Output is correct |
| 3 |
Correct |
2148 ms |
33692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2559 ms |
31808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1298 ms |
40016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
