oj.uz

Submission #164254

# Submission time Handle Problem Language Result Execution time Memory
164254 2019-11-18T20:38:15 Z luciocf Teams (CEOI11_tea) C++14
10 / 100
 2500 ms 70776 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 {-1e9-10, 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)
{
	for (int i = 1; i <= n; i++)
		dp[i] = opt[i] = -1e9-10;
 
	for (int i = 1; i <= 4*n; i++)
		tree[i] = {-1e9-10, 0};
 
 	dp[1] = (a[1].ff == 1 ? 1 : -1e9-10);
 	opt[1] = (a[1].ff == 1 ? 0 : -1e9-10);

	for (int i = 2; i <= n; i++)
	{
		if (i-a[i].ff < i-k || i-a[i].ff < 0) continue;

		if (i-a[i].ff == 0)
		{
			dp[i] = 1;
			opt[i] = 0;
		}
		else
		{
			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:119: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:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
tea.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i].ff);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23800 KB Output is correct
3 Incorrect 23 ms 23800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23804 KB Output is correct
2 Correct 23 ms 23800 KB Output is correct
3 Correct 24 ms 23900 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 24184 KB Output is correct
2 Correct 45 ms 24096 KB Output is correct
3 Incorrect 48 ms 24056 KB Integer -999999580 violates the range [1, 5000]

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 24056 KB Output is correct
2 Incorrect 45 ms 24056 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 486 ms 28520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 713 ms 29048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2556 ms 59132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2553 ms 70748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2532 ms 70776 KB Time limit exceeded
2 Halted 0 ms 0 KB -