Tòa nhà chọc trời

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một thành phố hình lưới có $n$ đường ngang (Đông) và $m$ đường dọc (Nam). Tại giao điểm của đường ngang thứ $i$ và đường dọc thứ $j$ có một tòa nhà chọc trời chiều cao $a_{i, j}$ .

Tại mỗi giao điểm $(i, j)$ , ta xét đường ngang thứ $i$ và đường dọc thứ $j$ — gồm $n + m - 1$ tòa nhà. Cần gán lại chiều cao cho $n + m - 1$ tòa nhà này, mỗi tòa được gán một số nguyên dương từ $1$ đến $x$ , sao cho:

Trong đường ngang thứ $i$ : thứ tự so sánh (lớn hơn / nhỏ hơn / bằng nhau) giữa hai tòa nhà bất kỳ được giữ nguyên so với chiều cao gốc.
Trong đường dọc thứ $j$ : thứ tự so sánh giữa hai tòa nhà bất kỳ cũng được giữ nguyên.
Giữa một tòa trên đường ngang và một tòa trên đường dọc (mà không phải là giao điểm) thì không có ràng buộc.

Với mỗi giao điểm $(i, j)$ , tìm giá trị $x$ nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ .

$n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên $a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$ — chiều cao các tòa nhà.

Dữ liệu ra

In ra $n$ dòng, mỗi dòng chứa $m$ số nguyên: giá trị $x$ nhỏ nhất tại mỗi giao điểm.

Ràng buộc

$1 \leq n, m \leq 1000$
$1 \leq a_{i, j} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
2 2 1 2 3 4	2 3 3 2	Tại $(1, 1)$ : ba tòa $1, 2, 3$ ở dòng 1 (giá trị $1, 2$ ) và cột 1 (giá trị $1, 3$ ) — nén còn ${1, 2, 2}$ cần $x = 2$ . Tại $(1, 2)$ : dòng 1 có $1 < 2$ , cột 2 có $2 < 4$ , đỉnh chung là $2$ — cần $x = 3$ .
2 3 1 2 1 2 1 2	2 2 2 2 2 2	Mỗi hàng và mỗi cột chỉ có $2$ giá trị phân biệt, nên không thể giảm $x$ xuống dưới $2$ tại bất kỳ giao điểm nào.

Bình luận

Không có bình luận tại thời điểm này.