Problem

4/6

estándar:: fusionar

Theory Click to read/hide

fusionar: una función que fusiona dos matrices ordenadas, es decir, en tiempo lineal obtiene una matriz ordenada, que consta de los elementos de la primera y la segunda matriz.
Se necesitan 5 argumentos: dos límites para cada matriz y el límite izquierdo del destino (donde se colocarán los elementos de la matriz resultante).
Se pueden encontrar más detalles en la documentación.

Ejemplos: // las matrices de origen deben ordenarse vector a = { 1, 3, 5, 7 }; vector b = { 2, 4, 6 }; // necesita que el destino sea lo suficientemente grande vector c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // los elementos se pueden repetir a = {1, 2, 4, 4}; b = {2, 3, 3, 3, 4, 4}; c.redimensionar(10); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Esta función es muy útil en el contexto de la ordenación por fusión.

Problem

Dada una matriz A de tamaño n, donde n = 2m para alguna m natural.
Debe crear un árbol de ordenación fusionando esta matriz. 
Este es un árbol binario donde las hojas son los elementos de una matriz, y cada nodo interno contiene una matriz ordenada que consiste en aquellos elementos de la matriz cuyas hojas están en un subárbol de este nodo (ver ejemplos para comprender).
Los nodos del árbol se numeran desde la capa inferior (capa hoja) hasta la parte superior, dentro de la capa de izquierda a derecha. La numeración parte del uno y es continua. Si la hoja tiene el número i, entonces contiene el valor Ai.
A continuación se muestra un ejemplo de numeración de árboles para n = 4.

     7
    / \
   /   \
  5    6
 / \    /  \
1 2 3   4

Entrada:
La primera línea contiene el número n (2 <= n <= 215) - el tamaño de la matriz A.
La siguiente línea contiene n enteros Ai (-109 <= A_i <= 109) - elementos de matriz.

Salida:
Imprime 2*n-1 líneas: la i-ésima línea contiene los elementos contenidos en el i-ésimo nodo del árbol.

Ejemplo:
 

Explicación:

   [-322, 5, 10, 97]
      /           \
     /              \
 [-322, 97]   [5, 10]
  /          \       /     \
[97]   [-322] [5]   [10]
 

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Entrada Salida
4
97 -322 5 10 		97
-322
5
10
-322 97
5 10
-322 5 10 97
Write the program below 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // ускорение ввода и вывода
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	vector<vector<int>> tree(2 * n - 1);
	for (int i = 0; i < n; i++)
		tree[i] = { arr[i] };

	int child = 0;
	for (int i = n; i < tree.size(); i++) {   
		child += 2;
	}

	for (int i = 0; i < tree.size(); i++) {
		for (int j = 0; j < tree[i].size(); j++)
			cout << tree[i][j] << ' ';
		cout << endl;
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!