# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
164243 |
2019-11-18T20:28:52 Z |
luciocf |
Teams (CEOI11_tea) |
C++14 |
|
2500 ms |
70824 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
const int maxn = 1e6+10;
int n;
pair<int, int> a[maxn];
int dp[maxn], opt[maxn];
pair<int, int> tree[4*maxn];
vector<int> team[maxn];
void upd(int node, int l, int r, int pos, int v)
{
if (l == r)
{
tree[node] = {v, l};
return;
}
int mid = (l+r)>>1;
if (pos <= mid) upd(2*node, l, mid, pos, v);
else upd(2*node+1, mid+1, r, pos, v);
tree[node] = max(tree[2*node], tree[2*node+1]);
}
pair<int, int> query(int node, int l, int r, int a, int b)
{
if (l > b || r < a) return {0, 0};
if (l >= a && r <= b) return tree[node];
int mid = (l+r)>>1;
return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}
int qtd(int k)
{
memset(dp, 0, sizeof dp);
memset(opt, 0, sizeof opt);
for (int i = 1; i <= 4*n; i++)
tree[i] = {0, 0};
for (int i = 1; i <= n; i++)
{
if (i-a[i].ff < i-k) continue;
pair<int, int> pp = query(1, 1, n, max(1, i-k), i-a[i].ff);
dp[i] = 1+pp.first, opt[i] = pp.second;
upd(1, 1, n, i, dp[i]);
}
return dp[n];
}
int main(void)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i].ff);
a[i].ss = i;
}
sort(a+1, a+n+1);
int ans = qtd(n);
int ini = 1, fim = n, ans2 = n;
while (ini <= fim)
{
int mid = (ini+fim)>>1;
if (qtd(mid) == ans) ans2 = mid, fim = mid-1;
else ini = mid+1;
}
qtd(ans2);
int aux = 0;
for (int i = n; i >= 1; )
{
++aux;
int j;
for (j = i; j > opt[i]; j--)
team[aux].push_back(a[j].ss);
i = j;
}
printf("%d\n", ans);
for (int i = 1; i <= ans; i++)
{
printf("%d", team[i].size());
for (auto x: team[i])
printf(" %d", x);
printf("\n");
}
}
Compilation message
tea.cpp: In function 'int main()':
tea.cpp:109:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d", team[i].size());
~~~~~~~~~~~~~~^
tea.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
tea.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i].ff);
~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
31608 KB |
Output is correct |
2 |
Incorrect |
37 ms |
31612 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
33 ms |
31608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
36 ms |
31608 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
55 ms |
31884 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
58 ms |
31884 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
806 ms |
35720 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
769 ms |
36104 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2538 ms |
60956 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2551 ms |
70776 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2543 ms |
70824 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |