題目連結：D. Minimax Problem

time limit per test:5 seconds memory limit per test:512 megabytes inputstandard input outputstandard output

You are given n arrays a1, a2, …, an; each array consists of exactly m integers. We denote the y-th element of the x-th array as ax,y.

You have to choose two arrays ai and aj(1≤i,j≤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∈[1,m] bk=max(ai,k,aj,k).

Your goal is to choose i and j so that the value of $\sum_{k=1}^m$bk is maximum possible.

Input

The first line contains two integers n and m (1≤n≤3⋅105, 1≤m≤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 ax represented by m integers ax,1, ax,2, …, ax,m (0≤ax,y≤10^9^).

Output

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

Example

input

複制

output

1 5

複制

題目大意

給你兩個數，n和m，表示n個數組每個數組有m個元素，然後讓你輸出任意兩個數組合并後數組中的最小值最大是幾，合并的規則是兩個數組的同一個位置取最大值，比如：1 2 3 4 5 和 5 4 3 2 1這兩個數列合并後的值為 5 4 3 4 5；最小值時3；

解題思路

既然是求最小值最大，那麼很容易想到二分，但是我們該如何check呢？當行很大，列很小的時候很容易想到狀壓，但是如何表示狀态呢？，既然是兩個數列合并後的最小值都要大于二分的 mid，是以用二進制來表示每個數列滿足要求的狀态，比如說一共4個數現在需要合并後的值大于等于3 兩個數列是 1 3 4 1 那麼這個數列滿足大于等于3的值可以用6表示（第2位和第3位大于等于三，也就是二進制的第二位和第三位唯一，結果是6），另一個是4 1 3 4 狀态表示為11，然後6|11等于列數4是以可以，如果不等那就不成立，現在我們check和二分都有了，就可以碼代碼了。

代碼

#include<bits/stdc++.h>
using namespace std;
int a[500000][10];//存圖 
int ans[1000];//判斷這個狀态是否成立 
int ans_pos[1000];//表示這個成立這個狀态是第幾行 
int n,m;
int ans1,ans2;//記錄成立的兩個狀态 
bool check(int x)
{
    int t;
    memset(ans,0,sizeof ans);//每次初始化狀态數組 
    for(int i=1;i<=n;i++)
    {
        t=0;//記錄狀态 
        for(int j=0;j<m;j++)
        {                            //這裡的 位運算 | 簡化了互相的加法，不懂得自己模拟一遍 
            if(a[i][j]>=x) t|=(1<<j);// j的第幾個元素滿足情況，第幾位為 1 
        }
        ans[t]=1;//這個狀态存在，就唯一； 
        ans_pos[t]=i;//記錄這個狀态是第幾行； 
    }
    int k=1<<m;//一共 m 列如果都是 1 那麼 二進制就是 m 個1 
    for(int i=0;i<k;i++)
    {
        if(!ans[i]) continue;//如果這個狀态為0，說明不存在 
        for(int j=0;j<k;j++)
        {
            if(!ans[j]) continue;
            if((i|j)==k-1)//如果 兩個位置 或 後等于k，那麼說明情況合法 
            {
                ans1=ans_pos[i];//ans1 ans2 滿足此狀态的兩行行數 
                ans2=ans_pos[j];// 
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        cin>>a[i][j];
    }
    int l=0,r=0x3f3f3f3f;
    int mid;
    while(l<=r)//二分模闆寫法 
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<ans1<<" "<<ans2<<'\n';
    return 0;
}

複制

D. Minimax Problem題目連結：D. Minimax Problem

題目連結：D. Minimax Problem

題目大意

解題思路

代碼