Submission #242686

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

swap

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

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

void get(vector<int> &aux, int u, int v, int f1, int x1, int f2, int x2)
{
	aux.clear();
	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]);
}

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

	vector<int> aux;

	for (int u = n; u >= 1; u--)
	{
		for (auto pp: anc[u])
		{
			int v = pp.first, ind = pp.second;

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

			get(aux, 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]];

				get(aux, u, a[r[u]], f1, x1, f2, x2);

				dp[u][ind] = min(dp[u][ind], aux);
			}

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

				get(aux, u, a[l[u]], f1, x1, f2, x2);

				dp[u][ind] = min(dp[u][ind], aux);
			}

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

				get(aux, u, a[r[u]], f1, x1, f2, x2);

				dp[u][ind] = min(dp[u][ind], aux);
			}
		}
	}

	for (auto x: dp[1][anc[1][a[1]]])
		printf("%d ", x);

	printf("\n");
}

Compilation message (stderr)

swap.cpp: In function 'void get(std::vector<int>&, int, int, int, int, int, int)':
swap.cpp:41: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:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = ptr; i < dp[f1][ind1].size(); i++)
                    ~~^~~~~~~~~~~~~~~~~~~~~
swap.cpp:55: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:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:65: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