oj.uz

답안 #242668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242668 2020-06-28T21:41:24 Z luciocf Swap (BOI16_swap) C++14
0 / 100
 107 ms 188280 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 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");
}

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: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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 188280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 188280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 188280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 188280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 188280 KB Output isn't correct
2 Halted 0 ms 0 KB -