Submit solution
Points:
1.25 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một ma trận ~a~ kích thước ~n \times n~ chỉ gồm các giá trị ~\{-2, -1, 0, 1, 2\}~. Các hàng của ma trận ~a~ được đánh số từ ~1~ đến ~n~ từ trên xuống dưới. Các cột của ma trận ~a~ được đánh số từ ~1~ đến ~n~ từ trái sang phải. Phần tử ở hàng ~i~, cột ~j~ được ký hiệu là ~a_{i,j}~.
Bảng ~a~ được gọi là tương thích với dãy ~t = (t_1, t_2, \ldots, t_n)~ nếu với mọi ~(i, j)~ với ~1 \leq i, j \leq n~:
- ~a_{i,j} = 0 \leftrightarrow t_i = t_j~.
- ~a_{i,j} = 1 \leftrightarrow t_i < t_j~.
- ~a_{i,j} = 2 \leftrightarrow t_i \leq t_j~.
- ~a_{i,j} = -1 \leftrightarrow t_i > t_j~.
- ~a_{i,j} = -2 \leftrightarrow t_i \geq t_j~.
Yêu cầu: cho trước ma trận ~a~, hãy tìm dãy số nguyên dương ~t~ tương thích với ~a~, sao cho giá trị lớn nhất của dãy ~t~ là nhỏ nhất có thể. Biết rằng luôn tồn tại một dãy ~t~ như vậy.
Input
- Dòng ~1~: Số nguyên dương ~n~.
- ~n~ dòng tiếp theo, mỗi dòng chứa đúng ~n~ số nguyên dương thể hiện ma trận ~a~.
Output
- Dòng ~1~: Ghi ra số lớn nhất của dãy ~t~.
- Dòng ~2~: Ghi ra ~n~ số nguyên dương thể hiện dãy ~t~. Nếu có nhiều dãy thỏa mãn có cùng giá trị lớn nhất, bạn được in ra một dãy bất kì.
Giới hạn
- Trong ~30\%~ số lượng test (trị giá ~30~ điểm): ~n \le 7~
- Trong ~70\%~ số lượng test còn lại (trị giá ~70~ điểm): ~n \le 77~
Sample Input
3
0 1 1
-1 0 1
-1 -1 0
Sample Output
3
1 2 3
Comments