You are given 𝑛 arrays 𝑎1, 𝑎2, ..., 𝑎𝑛; each array consists of exactly 𝑚 integers. We denote the 𝑦-th element of the 𝑥-th array as 𝑎𝑥,𝑦.

You have to choose two arrays 𝑎𝑖 and 𝑎𝑗 (1≤𝑖,𝑗≤𝑛, it is possible that 𝑖=𝑗). After that, you will obtain a new array 𝑏 consisting of 𝑚 integers, such that for every $k \in [1, m]$ $b_k = \max(a_{i, k}, a_{j, k})$ .

Your goal is to choose $𝑖$ and $𝑗$ so that the value of min$\min \limits_{k = 1}^{m} b_k$ is maximum possible.

#### 大致题意 📖

$i,j$，使$s$最大

#### 链接 🔗

「CodeForces 1288D」 Minimax Problem

#### 代码

const int maxd = 3e5+10;
ll a[maxd][10],ansl,ansr,n,m,vis[300];
bool check(ll x)
{
memset(vis,0,sizeof(vis));
FOR(i,1,n)
{
ll now = 0;
FOR(j,1,m) if(a[i][j] >= x) now |= 1<<(j-1);
vis[now] = i;
}
F(1<<m)
FOR(j,0,(1<<m)-1)
if(vis[i] && vis[j] && ( (i|j) == (((1<<m)-1))))
{
ansl = vis[i], ansr = vis[j];
return true;
}
return false;
}
int main()
{
//    __IN;__OUT;
RLL2(n ,m);
FOR(i,1,n) FOR(j,1,m) RLL(a[i][j]);
ll l = 0,r = 1e9;
while(l<=r)
{
ll x = (l+r)>>1;
if(check(x)) l = x+1;
else r = x-1;
}
PLN2(ansl,ansr);
return 0;
}