Saddle Points
mediumMatrix+20 XPTime limit 2s
A cell is a saddle point if its value is the smallest in its row and also the largest in its column (ties are allowed: "smallest" means no value in the row is smaller, "largest" means no value in the column is larger). Think of a mountain pass — the lowest point along one direction, the highest along the other.
Print every saddle point.
Input:
- line 1:
r c - next
rlines:cintegers each
Output: each saddle point as row col (1-based) on its own line, in row-major order (top to bottom, then left to right) — or -1 if there are none.
Constraints: 1 ≤ r, c ≤ 500, −10⁹ ≤ value ≤ 10⁹.
Think about it: checking each cell against its whole row and column costs O(r·c·(r + c)). Instead compute every row minimum and every column maximum once; a cell is a saddle point when it equals both.
Sample input 1
3 3 3 8 7 2 1 5 1 0 4
Sample output 1
1 1
Sample input 2
2 2 1 2 3 4
Sample output 2
2 1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).