Tìm kiếm trên ma trận sắp xếp

General
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Submissions
Đề bài

Cho một ma trận $M \times N$ chứa các số nguyên phân biệt sao cho mỗi hàng tăng dần từ trái sang phải, và phần tử đầu tiên của mỗi hàng luôn lớn hơn phần tử cuối cùng của hàng ngay trước nó. Cho $Q$ truy vấn, mỗi truy vấn là một số nguyên $x$. Hãy tìm tọa độ hàng và cột (đánh số từ $1$) của $x$ trong ma trận, hoặc in ra -1 nếu không tồn tại.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $M, N, Q$.
  • $M$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên.
  • $Q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $x$.
Dữ liệu ra
  • Gồm $Q$ dòng: nếu tìm thấy in r c (chỉ số hàng và cột từ $1$), ngược lại in -1.
Ví dụ
Input Output
3 4 3\n1 3 5 7\n10 11 16 20\n23 30 34 60\n3\n13\n60 1 2\n-1\n3 4
Giới hạn
  • $1 \le M, N \le 500$, $1 \le Q \le 10^5$
  • $|a_{i,j}|, |x| \le 10^9$
Draft saved