--->
16 задач
<---
Источники
#113894
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes
Петя увлёкся алгоритмами сжатия данных. Он уже изучил форматы gz , bz , zip и несколько других. Воодушевившись новыми знаниями, Петя собрался разработать свой формат сжатия и назвать его dis .
Петя решил сжимать таблицы. У него есть таблица, состоящая из n строк и m столбцов, заполненная целыми положительными числами. Он хочет заменить значения элементов таблицы на целые положительные числа так, чтобы отношение элементов в каждой строке и каждом столбце не изменилось. То есть, если в некоторой строке исходной таблицы a i , j < a i , k , то и в сжатой таблице a ' i , j < a ' i , k , и если a i , j = a i , k , то a ' i , j = a ' i , k . Аналогично, если в некотором столбце исходной таблицы a i , j < a p , j , то и в сжатой таблице a ' i , j < a ' p , j , и если a i , j = a p , j , то a ' i , j = a ' p , j .
Поскольку б'{о}льшие значения требуют больше места для хранения, максимальное значение элемента получившейся матрицы должно быть как можно меньше.
В теории Петя мастер, но вот писать код он не любит. Помогите ему реализовать формат сжатия dis .
Входные данные
В первой строке входных данных содержатся два числа
n
и
m
(
— количество строк и столбцов таблицы соответственно.
В следующих n строках содержится по m целых чисел a i , j (1 ≤ a i , j ≤ 10 9 ) — значения элементов таблицы.
Выходные данные
Выведите сжатую таблицу: n строк, содержащих по m чисел.
Если существует несколько ответов, минимизирующих максимальное число, то разрешается вывести любой из них.
Система оценки
Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Примечание
В первом примере a 1, 2 ≠ a 2, 1 , но, поскольку они не располагаются в одной строке или в одном столбце, при сжатии их можно сделать равными.
Примеры
Входные данные
2 2 1 2 3 4
Выходные данные
1 2 2 3
Входные данные
4 3 20 10 30 50 40 30 50 60 70 90 80 70
Выходные данные
2 1 3 5 4 3 5 6 7 9 8 7
Выбрано
:
|