Description
描述
给出一个 $n$ 行 $m$ 列的数字矩阵 $a$，找出两行 $x, y$，令 $b_j = max(a_{x, j}, a_{y, j})$，试使得 $maxlimits_{1 le j le m}b_j$ 最大，输出选择的 $x, y$，可以相同。
输入
第一行是 $n, m(1 le n le 3 cdot 10^5, 1 le m le 8)$。
后面是一个 $n$ 行 $m$ 列的矩阵 $a$，$0 le a_{i,j} le 10^9$。
输出
两个数 $x, y$，表示选取第 $x$ 行和第 $y$ 行，多解输出任意解。
样例
输入
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 5
解释
$b = { 5, 3, 3, 6, 3 }$，最小值是 $3$，没有最小值更大的方案了。
Solution
看到要求 最小值的最大值，显然要想到 二分。
观察到 $m le 8$，是不是可以 二进制压位 呢？答案是肯定的。
比如我们在判断答案为 $mid$ 是否可行时，我们对每一行定义一个二进制数 $b_i$，这个其实是一个 bitset ，但因为位数太少直接 int 就能实现，当 $a_{i,j} ge mid$ 时，$b_i$ 的左数第 $j$ 位就是 $1$，否则为 $0$。例如，$mid = 3$，$a_i = { 3, 4, 1, 2 }$，那么 $b_i = 1100_{(2)}$。这时，我们将 $t_{b_{i}} gets i$，表示此状态的来源。
考虑枚举两个状态 $i, j$，如果 $i, j$ 状态都存在（可以通过先将 $t$ 初始化为 $0$，看 $t_i, t_j$ 是不是 $> 0$ 来实现），然后如果 $i operatorname{or} j = 11dots 11$，那么这两个状态就可以满足我们的需求了（因为这说明每个位置都能找到至少一个 $ge mid$ 的数字），将所选的两行数定为 $t_i$ 和 $t_j$ 即可。
代码如下，仅供参考：
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = 10;
int n, m, a[N][M], b[N], t[1 << M], x, y;
inline bool check(int mid)
{
memset(b, 0, sizeof b);
memset(t, 0, sizeof t);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
b[i] = (b[i] << 1) | (a[i][j] >= mid);
t[b[i]] = i;
}
for(int i = 1; i < (1 << m); i++)
for(int j = 1; j < (1 << m); j++)
if((i | j) == (1 << m) - 1 && t[i] && t[j])
{
x = t[i]; y = t[j];
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
int lb = -1, rb = 1e9;
while(lb < rb)
{
int mid = lb + rb + 1 >> 1;
if(check(mid)) lb = mid;
else rb = mid - 1;
}
cout << x << ' ' << y << endl;
return 0;
}