oj.uz

Submission #242686

# Submission time Handle Problem Language Result Execution time Memory
242686 2020-06-29T01:54:18 Z luciocf Swap (BOI16_swap) C++14
48 / 100
 402 ms 262148 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 180472 KB Output is correct
2 Correct 115 ms 180344 KB Output is correct
3 Correct 113 ms 180344 KB Output is correct
4 Correct 113 ms 180472 KB Output is correct
5 Correct 115 ms 180344 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 180472 KB Output is correct
2 Correct 115 ms 180344 KB Output is correct
3 Correct 113 ms 180344 KB Output is correct
4 Correct 113 ms 180472 KB Output is correct
5 Correct 115 ms 180344 KB Output is correct
6 Correct 119 ms 180472 KB Output is correct
7 Correct 129 ms 180344 KB Output is correct
8 Correct 115 ms 180344 KB Output is correct
9 Correct 112 ms 180472 KB Output is correct
10 Correct 132 ms 180344 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 180472 KB Output is correct
2 Correct 115 ms 180344 KB Output is correct
3 Correct 113 ms 180344 KB Output is correct
4 Correct 113 ms 180472 KB Output is correct
5 Correct 115 ms 180344 KB Output is correct
6 Correct 119 ms 180472 KB Output is correct
7 Correct 129 ms 180344 KB Output is correct
8 Correct 115 ms 180344 KB Output is correct
9 Correct 112 ms 180472 KB Output is correct
10 Correct 132 ms 180344 KB Output is correct
11 Correct 119 ms 181548 KB Output is correct
12 Correct 121 ms 181552 KB Output is correct
13 Correct 167 ms 181624 KB Output is correct
14 Correct 143 ms 181516 KB Output is correct
15 Correct 116 ms 181496 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 180472 KB Output is correct
2 Correct 115 ms 180344 KB Output is correct
3 Correct 113 ms 180344 KB Output is correct
4 Correct 113 ms 180472 KB Output is correct
5 Correct 115 ms 180344 KB Output is correct
6 Correct 119 ms 180472 KB Output is correct
7 Correct 129 ms 180344 KB Output is correct
8 Correct 115 ms 180344 KB Output is correct
9 Correct 112 ms 180472 KB Output is correct
10 Correct 132 ms 180344 KB Output is correct
11 Correct 119 ms 181548 KB Output is correct
12 Correct 121 ms 181552 KB Output is correct
13 Correct 167 ms 181624 KB Output is correct
14 Correct 143 ms 181516 KB Output is correct
15 Correct 116 ms 181496 KB Output is correct
16 Runtime error 402 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 120 ms 180472 KB Output is correct
2 Correct 115 ms 180344 KB Output is correct
3 Correct 113 ms 180344 KB Output is correct
4 Correct 113 ms 180472 KB Output is correct
5 Correct 115 ms 180344 KB Output is correct
6 Correct 119 ms 180472 KB Output is correct
7 Correct 129 ms 180344 KB Output is correct
8 Correct 115 ms 180344 KB Output is correct
9 Correct 112 ms 180472 KB Output is correct
10 Correct 132 ms 180344 KB Output is correct
11 Correct 119 ms 181548 KB Output is correct
12 Correct 121 ms 181552 KB Output is correct
13 Correct 167 ms 181624 KB Output is correct
14 Correct 143 ms 181516 KB Output is correct
15 Correct 116 ms 181496 KB Output is correct
16 Runtime error 402 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -