Problem

4/6

std::merge

Theory Click to read/hide

merge - una funzione che unisce due array ordinati, vale a dire, in tempo lineare ottiene un array ordinato, che consiste degli elementi del primo e del secondo array.
Richiede 5 argomenti: due limiti per ciascun array e il limite sinistro della destinazione (dove verranno posizionati gli elementi dell'array risultante).
Ulteriori dettagli sono disponibili nella documentazione.

Esempi: // gli array di origine devono essere ordinati vettore a = { 1, 3, 5, 7 }; vettore b = { 2, 4, 6 }; // necessita che la destinazione sia abbastanza grande vettore c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // gli elementi possono essere ripetuti un = {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]  Questa funzione è molto utile nel contesto del merge sort.

Problem

Dato un array A di dimensione n, dove n = 2m per qualche m naturale.
Devi creare un albero di ordinamento unendo questo array. 
Questo è un albero binario in cui le foglie sono gli elementi di un array e ogni nodo interno contiene un array ordinato costituito da quegli elementi dell'array le cui foglie sono in un sottoalbero di questo nodo (vedi esempi per capire).
I nodi dell'albero sono numerati dal livello inferiore (strato foglia) verso l'alto, all'interno del livello da sinistra a destra. La numerazione parte da uno ed è continua. Se il foglio ha il numero i, allora contiene il valore Ai.
Di seguito è riportato un esempio di numerazione degli alberi per n = 4.

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

Inserimento:
La prima riga contiene il numero n (2 <= n <= 215) - la dimensione dell'array A.
La riga successiva contiene n numeri interi Ai (-109 <= A_i <= 109) - elementi dell'array.

Uscita:
Stampa 2*n-1 righe - la i-esima riga contiene gli elementi contenuti nell'i-esimo nodo dell'albero.

Esempio:
 
Input Uscita
4
97 -322 5 10 		97
-322
5
10
-322 97
5 10
-322 5 10 97


Spiegazione:

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