eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Угощения коров

Угощения коров

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Коровы отпраздновали еще один знаменательный месяц рекордного производства молока. Таким образом каждая из них заработала особое угощение. Коровы полностью заполнили прямоугольник w * h в ожидании угощения.

Каждая корова обладает уникальным достоинством F[rc] (1F[rc]1000000) которое обозначает ее общий показатель производства молока. Фермер Джон считает, что было бы справедливо расставить приоритеты по раздаче угощений, в первую очередь вознаграждая коров с высокой продуктивностью. Он планирует пройти прямоугольное поле по строкам, начиная раздавать угощения коровам с начала строки 1, потом с начала строки 2 и так далее.

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

Он попросил коров реорганизовать себя так, чтобы коровы с лучшей продуктивностью были вознаграждены первыми. Коровы, однако, не очень хороши в организации. Они могут поменять местами две строки или два столбца своего формирования. Фермер Джон попросил их сделать все возможное, переместив лучшую корову в верхний левый угол (строка 1, столбец 1), следующую лучшую корову в ряду 1, столбец 2 (если возможно) и так далее. Конечно, коровы не могут полностью отсортировать себя, но они могут сделать все возможное, следуя такой эвристике:

  • определить порядок вознаграждения Фермера Джона:

prb8669.gif
  • найдите корову с самым высоким рейтингом. Поменяйте местами строки и столбцы, пока она не окажется в строке 1, столбце 1. Никогда не двигайте ее снова.

  • Потом выполняйте следующее правило до тех пор, пока можно переставить как можно больше коров:

Найдите следующую корову с самым высоким рейтингом. Поменяйте местами строки и столбцы (при этом не перемещая коров с более высоким рейтингом) так, чтобы переместить ее в наилучшее возможное место, которое все еще доступно (например, строка 1, столбец 2, если оно доступно, или строка 2, столбец 1, если в первой строке нет свободных слотов).

Например, рассмотрим множество из 3 * 4 коров:

prb8667_1.gif

Корова с рейтингом 99 явно имеет самый высокий рейтинг, расположим ее в левом верхнем углу. Для этого поменяем местами строки 1 и 2, затем поменяем местами столбцы 1 и 2 (или наоборот - ответ такой же):

prb8667_2.gif

Корова с рейтингом 11 должна быть вознаграждена как можно скорее после коровы с самым высоким рейтингом. Она сейчас в ячейке (3, 4) - в последней ячейке, которая будет вознаграждена. На этом этапе уже слишком поздно менять ее на первый ряд или даже на первый столбец. Ей нужно перейти в (2, 2), поменяв местами столбцы 2 и 4, а затем поменяв местами строки 2 и 3:

prb8667_3.gif

Корова с рейтингом 10 получает вознаграждение сразу после коровы с 11. Корова 9 уже вознаграждена. Корова с 8 присуждается сразу после коровы с 10. Корова с 7 получает вознаграждение сразу после коровы с 8. Корова с 6 уже вознаграждена. Корову с 5 лучше всего переместить в строку 3, столбец 2, но строки 1 и 2 заморожены, как и все столбцы. Таким образом, коровы 1, 4 и 5 не двигаются, и вторая диаграмма выше - "лучшее, что могут сделать коровы".

Реализуйте этот алгоритм для других прямоугольных массивов коров.

Вхідні дані

Первая строка содержит два целых числа w и h (1w25, 1h25). Каждая из следующих h строк содержит w целых чисел F[ic] (1cw).

Вихідні дані

Выведите h строк. Каждая строка содержит w целых чисел, задающих ряд коров в окончательном их расположении.

Приклад

Вхідні дані #1
4 3
5 7 4 1
9 99 2 6
8 3 10 11
Вихідні дані #1
99 6 2 9
3 11 10 8
7 1 4 5
Джерело 2011 USACO Bronze Division, Февраль