Задача №114563. Почти отказоустойчивая база данных
Вы храните в базе данных массив длины \(m\). Чтобы обезопасить данные от случайного повреждения, база данных хранит не одну, а \(n\) физических копий хранимой информации.
К сожалению, недавно в базе данных произошла масштабная авария, которая потенциально изменила информацию в каждой копии.
Предполагается, что инцидент поменял не более одного элемента в каждой копии. Вам нужно восстановить исходный массив из текущего состояния базы данных.
Если существует несколько способ восстановления, найдите любой. Если нет ни одного массива, отличающегося от каждой копии не более чем в одной позиции, сообщите об этом.
В первой строке заданы два целых числа \(n\) и \(m\) (\(2 \le n\), \(1 \le m\), \(n \cdot m \le 250\,000\)) — количество физических копий исходной информации и размер массива исходной информации, соответственно.
В каждой из следующих \(n\) строк задан массив из \(m\) чисел \(s_j\) (\(1 \le s_j \le 10^9\)) — очередная физическая копия в базе данных после аварии.
Если можно восстановить массив, который мог бы представлять исходную информацию, то выведите в первой строке слово « Yes », и во второй строке сам массив из ровно \(m\) чисел от \(1\) до \(10^9\).
Если возможных ответов несколько, то выведите любой.
Если ни одного ответа нет, то выведите в единственной строке слово « No ».
В первом примере из условия массив \([1, 10, 100]\) отличается от каждого из трёх данных физических копий ровно в одной позиции.
Во втором примере из условия массив \([1, 1, 1, 1, 1, 1, 1]\) равен восьмой физической копии и отличается от каждой из первых семи физических копий ровно в одной позиции.
В третьем примере из условия невозможно найти какой-нибудь массив, который отличается не более чем в одной позиции от обеих физических копий после аварии.
В данной задаче \(100\) тестов, помимо тестов из условия, каждый из них оценивается в \(1\) балл. Результаты работы ваших решений на первых \(70\) тестах будут доступны во время соревнования. Результаты работы на остальных \(30\) будут доступны после окончания соревнования.
Пусть \(S = \max_{1 \le i \le n, 1 \le j \le m}{s_{i,j}}\).
Решения, корректно работающие при \(S \le 2, n, m \le 10\), наберут не менее \(10\) баллов.
Решения, корректно работающие при \(n, m \le 10\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(n, m \le 500\), наберут не менее \(40\) баллов.
Решения, корректно работающие при \(S \le 50\), наберут не менее \(40\) баллов (включая \(10\) баллов за тесты, в которых выполнено \(S \le 2, n, m \le 10\)).
3 3 1 100 100 1 1 100 10 10 100
Yes 1 10 100
8 7 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
Yes 1 1 1 1 1 1 1
2 3 1 1 1 2 2 2
No