Олимпиадный тренинг

Задача . std::merge


Задача

Темы:
Дан массив А размера 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
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w647
Комментарий учителя

Ваш ответ

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;
}
     

Загруженные файлы
Нет