В данной задаче нужно реализовать массив переменного размера, в который можно дописывать элементы, не зная заранее его окончательный размер. Используя эту структуру данных, нужно решить приведённую ниже задачу. В первой строке записано целое число -

Добавлена: 13.04.2026
Обновлена: 13.04.2026
Предмет: Программирование
Автор: Кэмп

#Основы алгоритмизации и программирования
#Структуры и алгоритмы обработки данных

Условие:

В данной задаче нужно реализовать массив переменного размера, в который можно дописывать элементы, не зная заранее его окончательный размер. Используя эту структуру данных, нужно решить приведённую ниже задачу.

В первой строке записано целое число $N$ - количество записей ( $1 \leqslant N \leqslant 2 \cdot 10^{5}$ ). В остальных $N$ строках содержатся записи, по одной в строке.

Для каждой записи указаны ключ и значение через пробел. Ключ - это целое число в диапазоне от 0 до $10^{6}$ включительно, а значение - это строка от одного до семи символов включительно, состоящая только из маленьких букв латинского алфавита.

Требуется вывести ровно те же самые $N$ записей, но в другом порядке. Записи должны быть упорядочены по возрастанию ключа. Если у нескольких записей ключ равный, то нужно упорядочить их в том порядке, в котором они встречаются по входном файле.

Важно: Решать задачу нужно следующим образом (другие решения засчитываться не будут). Нужно завести $10^{6}$ массивов переменного размера, и в каждый $k$ -ый массив складывать все записи с ключом, равным $k$ . После раскидывания записей по массивам достаточно будет пробежаться по массивам в порядке увеличения $k$ и распечатать их.

\begin{table} \captionsetup{labelformat=empty} \caption{Пример} \begin{array}{|l|l|} \hline \ninput.txt & output.txt \\ \hline 7 & 1 a \\ \hline 3 qwerty & 2 hello \\ \hline 3 string & 3 qwerty \\ \hline 6 good & 3 string \\ \hline 1 a & 3 ab \\ \hline 3 ab & 5 world \\ \hline 2 hello & 6 good \\ \hline 5 world & \\ \hline \end{array} \end{table}

Решение:

Чтобы решить задачу с растущим массивом, мы можем использовать массивы переменного размера, чтобы хранить записи с одинаковыми ключами. Давайте рассмотрим решение по шагам.

Шаг 1: Дано

Входной файл: input.txt
Выходной файл: output.txt
Ограничения:
- $N$ — количество записей ( $1 \leqslant N \leqslant 2 \cdot 10^{5}$ )
- Ключ — целое число от 0 до $10^{6}$
- Значение — строка от 1 до 7 символов, состоящая из маленьких латинских букв