# Educational Codeforces Round 80. D - Minimax Problem

i可以等于j

0表示当前位置的值<x

1表示当前位置的值>=x

``` 1 /*
2 Written By. StelaYuri
3 On 2020/01/14
4 */
5 #include<bits/stdc++.h>
6 using namespace std;
7 int a[300050][10],b[300],n,m,ci,cj,cpd=0;
8 bool prim(int x){
9     int i,j,d;
10     memset(b,0,sizeof b);
11     for(i=1;i<=n;i++){
12         d=0;
13         for(j=0;j<m;j++)
14             if(a[i][j]>=x)
15                 d|=(1<<j);
16         b[d]=i;
17     }
18     for(i=0;i<=cpd;i++)
19         for(j=0;j<=cpd;j++)
20             if(b[i]&&b[j]&&((i|j)==cpd)){
21                 ci=b[i];
22                 cj=b[j];
23                 return true;
24             }
25     return false;
26 }
27 int main(){
28     ios::sync_with_stdio(0);
29     cin.tie(0);cout.tie(0);
30     int i,j,l=0,r=1e9,mid;
31     cin>>n>>m;
32     if(n==1){
33         cout<<"1 1\n";
34         return 0;
35     }
36     for(j=0;j<m;j++)
37         cpd|=(1<<j);
38     for(i=1;i<=n;i++)
39         for(j=0;j<m;j++)
40             cin>>a[i][j];
41     while(l<=r){
42         mid=(l+r)>>1;
43         if(prim(mid))
44             l=mid+1;
45         else
46             r=mid-1;
47     }
48     prim(r);//保险起见再处理一次
49     cout<<ci<<‘ ‘<<cj<<endl;
50
51     return 0;
52 }```

Educational Codeforces Round 80. D - Minimax Problem

(0)
(0)