Submission #242685

#	Time	Username	Problem	Language	Result	Execution time	Memory
242685		luciocf	Swap (BOI16_swap)	C++14	48 / 100	766 ms	262148 KiB

swap

#include <bits/stdc++.h>

using namespace std;

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

int a[maxn];

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

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

unordered_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];
	}
}

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

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

	for (int p = 0; ptr + (1<<p)-1 < dp[f2][ind2].size(); p++)
	{
		for (int i = ptr; i < ptr + (1<<p); i++)
			aux.push_back(dp[f1][ind1][i]);

		for (int i = ptr; i < ptr + (1<<p); i++)
			aux.push_back(dp[f2][ind2][i]);

		ptr += (1<<p);
	}

	for (int i = ptr; i < dp[f1][ind1].size(); i++)
		aux.push_back(dp[f1][ind1][i]);

	for (int i = ptr; i < dp[f2][ind2].size(); i++)
		aux.push_back(dp[f2][ind2][i]);

	return aux;
}

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

	vector<int> aux;

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

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

	aux = get(u, v, f1, x1, f2, x2);
	if (dp[u][ind].size() == 0) dp[u][ind] = aux;
	dp[u][ind] = min(dp[u][ind], 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 (dp[u][ind].size() == 0) dp[u][ind] = aux;
		dp[u][ind] = min(dp[u][ind], 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 (dp[u][ind].size() == 0) dp[u][ind] = aux;
		dp[u][ind] = min(dp[u][ind], 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 (dp[u][ind].size() == 0) dp[u][ind] = aux;
		dp[u][ind] = min(dp[u][ind], aux);
	}
}

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);

	printf("\n");
}

Compilation message (stderr)

swap.cpp: In function 'std::vector<int> get(int, int, int, int, int, int)':
swap.cpp:39:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int p = 0; ptr + (1<<p)-1 < dp[f2][ind2].size(); p++)
                  ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = ptr; i < dp[f1][ind1].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = ptr; i < dp[f2][ind2].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:115: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 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32