Задача

4/6

std::merge

Теория Нажмите, чтобы прочитать/скрыть

merge - функция, которая объединяет два отсортированных массива, а именно, за линейное время получает отсортированный массив, который состоит из элементов первого и второго массива.
Она принимает 5 аргументов: по две границы для каждого массива и левая граница места назначения (где будут расположены элементы результирующего массива).
Подробнее можете ознакомиться в документации.

Примеры: 

	// исходные массивы должны быть отсортированы
	vector a = { 1, 3, 5, 7 };
	vector b = { 2, 4, 6 };

	// необходимо, чтобы место назначения имело достаточный размер
	vector c(7); 
	
	merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
	// c = [1, 2, 3, 4, 5, 6, 7]


	// элементы могут повторяться
	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]
 Данную функцию очень удобно использовать в контексте сортировки слиянием.

Задача

Дан массив А размера n, где n = 2m для некоторого натурального m.
Вам необходимо построить дерево сортировки слиянием этого массива. 
Это бинарное дерево, где листами являются элементы массива, а каждый внутренний узел содержит отсортированный массив, состоящий из тех элементов массива, чьи листья находятся в поддереве этого узла (для понимания смотрите примеры).
Узлы дерева нумеруются от нижнего слоя (слой листьев) к верхнему, внутри слоя слева направо. Нумерация начинается с единицы и является сквозной. Если лист имеет номер i, то в нем располагается значение Ai.
Ниже показан пример нумерации дерева при n = 4.

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

Входные данные:
В первой строке дается число n (2 <= n <= 215) - размер массива А.
В следующей строки дано n целых чисел Ai (-109 <= A_i <= 109) - элементы массива.

Выходные данные:
Выведите 2*n-1 строк - в i-й строке элементы, содержащиеся в i-м узле дерева.

Пример:
 
Входные данные Выходные данные
4
97 -322 5 10		 97
-322
5
10
-322 97
5 10
-322 5 10 97


Пояснение:

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



time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Вставьте недостающие фрагменты кода
C++
Напишите программу ниже 
#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;
}

     

Результат проверки программы 

Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!