Educational Codeforces Round 80 D. Minimax Problem（二分，状态压缩）

题目链接

Educational Codeforces Round 80 D. Minimax Problem

思路

看到最小值最大我们很容易想到二分，看到$m$最大为$8$我们很容易想到状态压缩。

我们使用二分答案，考虑如何去check。

在check函数里面，我们将原矩阵中大于等于$mid$的值视为$1$，小于$mid$的值视为$0$。按照每一行进行二进制状压，因为$2^m$最大为$256$，因此我们直接使用桶来记录每一行状压的结果。

暴力枚举两种状态，如果这两种状态都出现过且$or$起来为$2^m-1$就满足条件。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 3e5 + 5, M = 10;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m;
int a[N][M], st[(1ll << 9)];
int qmi(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = res * a;
		b >>= 1;
		a = a * a;
	}
	return res;
}
bool check(int x, int &tx, int &ty)
{
	memset(st, 0, sizeof st);
	for (int i = 1; i <= n; i++)
	{
		int res = 0;
		for (int j = 1; j <= m; j++)
		{
			res = res * 2 + (a[i][j] >= x);
		}
		st[res] = i;
	}
	for (int i = 0; i <= qmi(2, m) - 1; i++)
	{
		for (int j = 0; j <= qmi(2, m) - 1; j++)
		{
			if (st[i] && st[j] && (i | j) == qmi(2, m) - 1)
			{
				tx = st[i], ty = st[j];
				return true;
			}
		}
	}
	return false;
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
		}
	}
	int low = 0, high = 1e9;
	int tx = 1, ty = 1;
	while (low < high)
	{
		int mid = low + high + 1 >> 1;
		if (check(mid, tx, ty))
		{
			low = mid;
		}
		else
		{
			high = mid - 1;
		}
	}
	cout << tx << " " << ty << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	// cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}