Codeforces Edu80. Div2. D

https://codeforces.com/contest/1288/problem/D

Problem - D - Codeforces

 

n=6 m=5
a1: 5 0 3 1 2
a2: 1 8 9 1 3
a3: 1 2 3 4 5
a4: 9 1 0 3 7
a5: 2 3 0 6 3
a6: 6 4 1 7 0

 

a수열 2개만 뽑아서 각 자리마다 max값을 취함. 이 수열을 c라고 하자.

c = { max(a11,a21), max(a12, a22), max(a13,a23), max(a14, a24), max(a15, a25) } 인 셈.

이제 수열 c값들의 minimum값을 구함.

이 min값의 최대값을 구하는 문제

 

min값을 이분탐색으로 추정한다.

그럼 이 min값 이상인 것들은 1이라 표시하고 미만인 것들은 0이라 표시하면

수열이 1과 0으로만 이루어진 상태가 된다.

n 제한이 30만이나 돼서 두 a수열의 OR(|) 결과가 111...1이 되는 것들을 찾기 힘들어 보이지만,

m 제한이 8밖에 안되므로 두 a수열의 OR(|) 결과값은 많아야 2^8 = 256개 만큼만 나오는 것을 알 수 있다.

 

그러므로 n개의 수열 a를 256개 이하의  1과 0으로 이루어진 수열로 줄여놓고

여기서 두 수열의 'OR(|)'값이 모두 1로 이루어진 것을 찾는다.

 

 

 

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
vector<vector<int>> a;
map<int,vector<int>> dic;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n,m; cin >> n >> m;
    a.clear(); a.resize(n, vector<int>(m));
    int mn=0x3f3f3f3f, mx=-1;
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> a[i][j];
            mn = min(mn, a[i][j]);
            mx = max(mx, a[i][j]);
        }
    }
 
    unsigned char mask = ((1<<m)-1);
    int lo=mn, hi=mx;
    int ansl, ansr;
    while(lo<=hi) {
        int mid = (lo+hi)/2;
        dic.clear();
        for(int i=0; i<n; i++) {
            int bit = 0;
            for(int j=0; j<m; j++) {
                if(a[i][j]>=mid) bit|=(1<<j);
            }
            dic[bit].push_back(i);
        }
 
        bool good =false;
        for(map<int,vector<int>>::iterator it = dic.begin(); it!=dic.end(); it++) {
            for(auto jt = it; jt!=dic.end(); jt++) {
                if((it->first | jt->first) == mask) {
                    good = true;
                    ansl = it->second[0];
                    ansr = jt->second[0];
                    break;
                }
            }
            if(good) break;
        }
 
        if(good) lo = mid+1;
        else hi = mid-1;
    }
    printf("%d %d\n", ansl+1, ansr+1);
    return 0;
}