Problem

4/6

std :: fusionner

Theory Click to read/hide

merge - une fonction qui fusionne deux tableaux triés, à savoir, en temps linéaire, elle obtient un tableau trié, qui se compose des éléments du premier et du deuxième tableau.
Il prend 5 arguments : deux bornes pour chaque tableau et la borne gauche de la destination (où les éléments du tableau résultant seront placés).
Plus de détails peuvent être trouvés dans la documentation.

Exemples: // les tableaux source doivent être triés vecteur a = { 1, 3, 5, 7 } ; vecteur b = { 2, 4, 6 } ; // besoin que la destination soit assez grande vecteur c(7); fusionner(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // les éléments peuvent être répétés un = {1, 2, 4, 4} ; b = { 2, 3, 3, 3, 4, 4 } ; c.resize(10); fusionner(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Cette fonction est très utile dans le cadre du tri par fusion.

Problem

Soit un tableau A de taille n, où n = 2m pour un m naturel.
Vous devez construire un arbre de tri en fusionnant ce tableau. 
Il s'agit d'un arbre binaire où les feuilles sont les éléments d'un tableau, et chaque nœud interne contient un tableau trié composé des éléments du tableau dont les feuilles sont dans un sous-arbre de ce nœud (voir les exemples pour comprendre).
Les nœuds de l'arbre sont numérotés de la couche inférieure (couche feuille) vers le haut, à l'intérieur de la couche de gauche à droite. La numérotation commence à partir de un et est continue. Si la feuille a le numéro i, alors elle contient la valeur Ai.
Ci-dessous un exemple de numérotation des arbres pour n = 4.

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

Saisie :
La première ligne contient le nombre n (2 <= n <= 215) - la taille du tableau A.
La ligne suivante contient n entiers Ai (-109 <= A_i <= 109) - éléments de tableau.

Sortie :
Imprimer 2*n-1 lignes - la ième ligne contient les éléments contenus dans le ième nœud de l'arbre.

Exemple :
 
Entrée Sortie
4
97 -322 5 10 		97
-322
5
10
-322 97
5 10
-322 5 10 97


Explication :

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