Problem

4/6

std::merge

Theory Click to read/hide

merge - uma função que mescla dois arrays ordenados, ou seja, em tempo linear obtém um array ordenado, que consiste nos elementos do primeiro e do segundo array.
Leva 5 argumentos: dois limites para cada array e o limite esquerdo do destino (onde os elementos do array resultante serão colocados).
Mais detalhes podem ser encontrados na documentação.

Exemplos: // matrizes de origem devem ser classificadas vetor a = { 1, 3, 5, 7 }; vetor b = { 2, 4, 6 }; // precisa que o destino seja grande o suficiente vetor c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // os elementos podem ser repetidos a = {1, 2, 4, 4}; b = { 2, 3, 3, 3, 4, 4 }; c.resize(10); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Esta função é muito útil no contexto de classificação por mesclagem.

Problem

Dada uma matriz A de tamanho n, onde n = 2m para algum m natural.
Você precisa construir uma árvore de classificação mesclando esta matriz. 
Esta é uma árvore binária onde as folhas são os elementos de um array, e cada nó interno contém um array ordenado consistindo daqueles elementos do array cujas folhas estão em uma subárvore deste nó (veja exemplos para compreensão).
Os nós da árvore são numerados da camada inferior (camada folha) até o topo, dentro da camada da esquerda para a direita. A numeração começa em um e é contínua. Se a folha tiver o número i, ela contém o valor Ai.
Abaixo está um exemplo de numeração de árvore para n = 4.

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

Entrada:
A primeira linha contém o número n (2 <= n <= 215) - o tamanho do array A.
A próxima linha contém n inteiros Ai (-109 <= A_i <= 109) - elementos da matriz.

Saída:
Imprima 2*n-1 linhas - a i-ésima linha contém os elementos contidos no i-ésimo nó da árvore.

Exemplo:
 
Entrada Saída
4
97 -322 5 10 		97
-322
5
10
-322 97
5 10
-322 5 10 97


Explicação:

   [-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++
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!