Codeforces Round #804 (Div. 2)
23:14:37 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
C. Хүснэгт шахах
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Бяцхан Петя одоо өгөгдөл шахалтын алгоритмуудад маш дуртай болсон. Тэр аль хэдийн $gz$, $bz$, $zip$ болон өөр олон алгоритмуудыг судалчихсан. Шинэ мэдлэгтээ урамшсан Петя одоо $dis$ гэж нэрлэхийг хүсэж буй шинэ шахалтын алгоритм хөгжүүлж байгаа.
Петя хүснэгтүүдийг шахахаар шийдсэн. Түүнд эерэг бүхэл тоогоор дүүргэсэн $n$ мөр $m$ баганатай $a$ хүснэгт өгөгдсөн. Тэр мөр болон багана бүрийн харьцангуй дараалал өөрчлөгдөхгүй байх эерэг бүхэл тооноос тогтох $a'$ хүснэгт бүтээхийг хүсч байна. Энэ нь анхны хүснэгтийн $i$-р мөрөнд $a_{i, j} < a_{i, k}$ байсан бол үүсч буй хүснэгтэнд $a'_{i, j} < a'_{i, k}$ байх ба хэрвээ $a_{i, j} = a_{i, k}$ байсан бол $a'_{i, j} = a'_{i, k}$ болно гэсэн үг. Үүнтэй адилаар анхны хүснэгтийн $j$-р багананд $a_{i, j} < a_{p, j}$ байсан бол шахагдсан хүснэгтэнд $a'_{i, j} < a'_{p, j}$ байх ба хэрвээ $a_{i, j} = a_{p, j}$ байсан бол $a'_{i, j} = a'_{p, j}$ болно гэсэн үг.
Том хэмжээний утгуудыг хадгалахад их зай эзлэх учир $a'$-д буй утгын хамгийн их нь аль болох бага байх хэрэгтэй.
Петя онолдоо сайн хэдий ч түүнд алгоритмаа хэрэгжүүлэхэд таны тусламж хэрэгтэй.
Оролт
Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ( байх ба харгалзан хүснэгтийн мөрийн тоо болон баганын тоо юм.
Дараагийн $n$ мөр бүрт $m$ ширхэг бүхэл тоон утгууд $a_{i, j}$ $(1 ≤ a_{i, j} ≤ 10^{9})$ байх ба хүснэгтэнд буй утгууд юм.
Гаралт
Мөр бүрт $m$ бүхэл тоон утга бүхий $n$ мөрөөс тогтох шахагдсан хүснэгтийг хэвлэ.
Хэрвээ шахагдсан хүснэгтэн дах хамгийн их утга боломжит хамгийн бага байх хэд хэдэн хариулт байвал та алийг нь ч хэвлэж болно.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
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
Тэмдэглэл
Эхний жишээн дээр $a_{1, 2} ≠ a_{2, 1}$ байгаа боловч нэг мөр эсвэл нэг баганад байрлаагүй учир шахалтын дараа тэнцүү болж болно.