Minimax Problem

题意翻译

给出一个 $n$ 行 $m$ 列的数字矩阵 $a$，找出两行 $x, y$，令 $b_j = \max(a_{x, j}, a_{y, j})$，试使得 $\min\limits_{1 \le j \le m}b_j$ 最大，输出选择的 $x, y$，可以相同。

题目描述

You are given $ n $ arrays $ a_1 $ , $ a_2 $ , ..., $ a_n $ ; each array consists of exactly $ m $ integers. We denote the $ y $ -th element of the $ x $ -th array as $ a_{x, y} $ . You have to choose two arrays $ a_i $ and $ a_j $ ( $ 1 \le i, j \le n $ , it is possible that $ i = j $ ). After that, you will obtain a new array $ b $ consisting of $ m $ integers, such that for every $ k \in [1, m] $ $ b_k = \max(a_{i, k}, a_{j, k}) $ . Your goal is to choose $ i $ and $ j $ so that the value of $ \min \limits_{k = 1}^{m} b_k $ is maximum possible.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \le n \le 3 \cdot 10^5 $ , $ 1 \le m \le 8 $ ) — the number of arrays and the number of elements in each array, respectively. Then $ n $ lines follow, the $ x $ -th line contains the array $ a_x $ represented by $ m $ integers $ a_{x, 1} $ , $ a_{x, 2} $ , ..., $ a_{x, m} $ ( $ 0 \le a_{x, y} \le 10^9 $ ).

输出格式

Print two integers $ i $ and $ j $ ( $ 1 \le i, j \le n $ , it is possible that $ i = j $ ) — the indices of the two arrays you have to choose so that the value of $ \min \limits_{k = 1}^{m} b_k $ is maximum possible. If there are multiple answers, print any of them.

输入输出样例

输入样例 #1

6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0

输出样例 #1

1 5

题意翻译

给出一个 $n$ 行 $m$ 列的数字矩阵 $a$，找出两行 $x, y$，令 $b_j = \max(a_{x, j}, a_{y, j})$，试使得 $\min\limits_{1 \le j \le m}b_j$ 最大，输出选择的 $x, y$，可以相同。