Module: STL algorithms


Problem

4/6

std::merge

Theory Click to read/hide

merge - a function that merges two sorted arrays, namely, in linear time it gets a sorted array, which consists of the elements of the first and second array.
It takes 5 arguments: two bounds for each array and the left bound of the destination (where the elements of the resulting array will be placed).
More details can be found in the documentation.

Examples: // source arrays must be sorted vector a = { 1, 3, 5, 7 }; vector b = { 2, 4, 6 }; // need destination to be large enough vector c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // elements can be repeated 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]  This function is very useful in the context of merge sort.

Problem

Given an array A of size n, where n = 2m for some natural m.
You need to build a sort tree by merging this array. 
This is a binary tree where the leaves are the elements of an array, and each internal node contains a sorted array consisting of those elements of the array whose leaves are in a subtree of this node (see examples for understanding).
Tree nodes are numbered from the bottom layer (leaf layer) to the top, inside the layer from left to right. The numbering starts from one and is continuous. If the sheet has the number i, then it contains the value Ai.
Below is an example of tree numbering for n = 4.

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

Input:
The first line contains the number n (2 <= n <= 215) - the size of the array A.
The next line contains n integers Ai (-109 <= A_i <= 109) - array elements.

Output:
Print 2*n-1 lines - the i-th line contains the elements contained in the i-th node of the tree.

Example:
 
Input Output
4
97 -322 5 10 		97
-322
5
10
-322 97
5 10
-322 5 10 97


Explanation:

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