제출 #242668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242668		luciocf	Swap (BOI16_swap)	C++14	0 / 100	107 ms	188280 KiB

swap

#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 false;
}

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;

	x1 = a[u], x2 = a[l[u]];

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

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

	x1 = a[u], x2 = a[r[u]];

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

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

	x1 = a[l[u]], x2 = a[u];

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

	aux = get(u, a[r[u]], f1, x1, f2, x2);
	if (r[u] && 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");
}

컴파일 시 표준 에러 (stderr) 메시지

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:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
swap.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32