oj.uz

Submission #242682

# Submission time Handle Problem Language Result Execution time Memory
242682 2020-06-29T01:17:54 Z luciocf Swap (BOI16_swap) C++14
48 / 100
 623 ms 262148 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int maxl = 38;

int a[maxn];

int pai[maxn];
int l[maxn], r[maxn];

vector<pii> dp[maxn][maxl];

map<int, int> anc[maxn];

void get_anc(int u)
{
	int ind = 0, v = u;

	while (v)
	{
		anc[u][a[v]] = ++ind;

		if (l[pai[v]] != v && l[pai[v]]) anc[u][a[l[pai[v]]]] = ++ind;

		v = pai[v];
	}
}

bool menor(vector<pii> a, vector<pii> b)
{
	if (!b.size()) return true;

	for (int i = 0; i < a.size(); i++)
	{
		if (a[i].ff < b[i].ff) return true;
		if (a[i].ff > b[i].ff) return false;
	}

	return true;
}

vector<pii> get(int u, int v, int f1, int x1, int f2, int x2)
{
	vector<pii> aux;
	aux.push_back({v, u});

	int ptr1 = 0, ptr2 = 0;
	int ind1 = anc[f1][x1], ind2 = anc[f2][x2];

	while (ptr1 < dp[f1][ind1].size() || ptr2 < dp[f2][ind2].size())
	{
		if (ptr1 == dp[f1][ind1].size())
		{
			aux.push_back(dp[f2][ind2][ptr2++]);
		}
		else if (ptr2 == dp[f2][ind2].size())
		{
			aux.push_back(dp[f1][ind1][ptr1++]);
		}
		else if (dp[f1][ind1][ptr1].ss < dp[f2][ind2][ptr2].ss)
		{
			aux.push_back(dp[f1][ind1][ptr1++]);
		}
		else
		{
			aux.push_back(dp[f2][ind2][ptr2++]);
		}
	}

	return aux;
}

void solve(int u, int v)
{
	if (!u || dp[u][anc[u][v]].size()) return;

	vector<pii> ans;

	int f1 = l[u], f2 = r[u];
	int x1 = a[f1], x2 = a[f2];

	solve(f1, x1); solve(f2, x2);

	vector<pii> aux = get(u, v, f1, x1, f2, x2);
	if (menor(aux, ans)) ans = aux;

	if (l[u] && r[u])
	{
		x1 = v, x2 = a[l[u]];

		solve(f1, x1); solve(f2, x2);

		aux = get(u, a[r[u]], f1, x1, f2, x2);
		if (menor(aux, ans)) ans = aux;
	}

	if (l[u])
	{
		x1 = v, x2 = a[r[u]];

		solve(f1, x1); solve(f2, x2);

		aux = get(u, a[l[u]], f1, x1, f2, x2);
		if (menor(aux, ans)) ans = aux;
	}

	if (r[u])
	{
		x1 = a[l[u]], x2 = v;

		solve(f1, x1); solve(f2, x2);

		aux = get(u, a[r[u]], f1, x1, f2, x2);
		if (menor(aux, ans)) ans = aux;
	}

	dp[u][anc[u][v]] = ans;
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	for (int i = 1; i <= n; i++)
	{
		if (2*i <= n) l[i] = 2*i;

		if (2*i+1 <= n) r[i] = 2*i+1;

		pai[i] = i/2;
	}

	for (int i = 1; i <= n; i++)
		get_anc(i);

	solve(1, a[1]);

	for (auto x: dp[1][anc[1][a[1]]])
		printf("%d ", x.ff);
	printf("\n");
}

Compilation message

swap.cpp: In function 'bool menor(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
swap.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++)
                  ~~^~~~~~~~~~
swap.cpp: In function 'std::vector<std::pair<int, int> > get(int, int, int, int, int, int)':
swap.cpp:57:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ptr1 < dp[f1][ind1].size() || ptr2 < dp[f2][ind2].size())
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:57:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ptr1 < dp[f1][ind1].size() || ptr2 < dp[f2][ind2].size())
                                       ~~~~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:59:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr1 == dp[f1][ind1].size())
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (ptr2 == dp[f2][ind2].size())
            ~~~~~^~~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 188152 KB Output is correct
2 Correct 115 ms 188280 KB Output is correct
3 Correct 117 ms 188152 KB Output is correct
4 Correct 116 ms 188284 KB Output is correct
5 Correct 117 ms 188388 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 188152 KB Output is correct
2 Correct 115 ms 188280 KB Output is correct
3 Correct 117 ms 188152 KB Output is correct
4 Correct 116 ms 188284 KB Output is correct
5 Correct 117 ms 188388 KB Output is correct
6 Correct 120 ms 188408 KB Output is correct
7 Correct 116 ms 188280 KB Output is correct
8 Correct 116 ms 188280 KB Output is correct
9 Correct 116 ms 188280 KB Output is correct
10 Correct 119 ms 188272 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 188152 KB Output is correct
2 Correct 115 ms 188280 KB Output is correct
3 Correct 117 ms 188152 KB Output is correct
4 Correct 116 ms 188284 KB Output is correct
5 Correct 117 ms 188388 KB Output is correct
6 Correct 120 ms 188408 KB Output is correct
7 Correct 116 ms 188280 KB Output is correct
8 Correct 116 ms 188280 KB Output is correct
9 Correct 116 ms 188280 KB Output is correct
10 Correct 119 ms 188272 KB Output is correct
11 Correct 133 ms 189688 KB Output is correct
12 Correct 131 ms 189652 KB Output is correct
13 Correct 131 ms 189564 KB Output is correct
14 Correct 128 ms 189560 KB Output is correct
15 Correct 134 ms 189560 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 188152 KB Output is correct
2 Correct 115 ms 188280 KB Output is correct
3 Correct 117 ms 188152 KB Output is correct
4 Correct 116 ms 188284 KB Output is correct
5 Correct 117 ms 188388 KB Output is correct
6 Correct 120 ms 188408 KB Output is correct
7 Correct 116 ms 188280 KB Output is correct
8 Correct 116 ms 188280 KB Output is correct
9 Correct 116 ms 188280 KB Output is correct
10 Correct 119 ms 188272 KB Output is correct
11 Correct 133 ms 189688 KB Output is correct
12 Correct 131 ms 189652 KB Output is correct
13 Correct 131 ms 189564 KB Output is correct
14 Correct 128 ms 189560 KB Output is correct
15 Correct 134 ms 189560 KB Output is correct
16 Runtime error 623 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 188152 KB Output is correct
2 Correct 115 ms 188280 KB Output is correct
3 Correct 117 ms 188152 KB Output is correct
4 Correct 116 ms 188284 KB Output is correct
5 Correct 117 ms 188388 KB Output is correct
6 Correct 120 ms 188408 KB Output is correct
7 Correct 116 ms 188280 KB Output is correct
8 Correct 116 ms 188280 KB Output is correct
9 Correct 116 ms 188280 KB Output is correct
10 Correct 119 ms 188272 KB Output is correct
11 Correct 133 ms 189688 KB Output is correct
12 Correct 131 ms 189652 KB Output is correct
13 Correct 131 ms 189564 KB Output is correct
14 Correct 128 ms 189560 KB Output is correct
15 Correct 134 ms 189560 KB Output is correct
16 Runtime error 623 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -