Submission #128356

#	Time	Username	Problem	Language	Result	Execution time	Memory
128356		tutis	Olympiads (BOI19_olympiads)	C++17	44 / 100	2023 ms	131244 KiB

olympiads

/*input
5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9
*/
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
using namespace std;
typedef long long ll;
int a[500][6];
int n, k, kth;
int value(vector<int>&x)
{
	int ret[6] = {0, 0, 0, 0, 0};
	for (int i : x)
	{
		for (int j = 0; j < k; j++)
			ret[j] = max(ret[j], a[i][j]);
	}
	int sum = 0;
	for (int j = 0; j < k; j++)
		sum += ret[j];
	return sum;
}
int value(ll xx)
{
	int ret[6] = {0, 0, 0, 0, 0};
	for (int t = 0; t < k; t++)
	{
		int i = xx % 512;
		xx /= 512;
		for (int j = 0; j < k; j++)
			ret[j] = max(ret[j], a[i][j]);
	}
	int sum = 0;
	for (int j = 0; j < k; j++)
		sum += ret[j];
	return sum;
}
ll convert(vector<int>&x)
{
	ll ret = 0;
	for (int i : x)
		ret = ret * 512 + i;
	return ret;
}
vector<int>deconvert(ll x)
{
	vector<int>ret;
	for (int i = 0; i < k; i++)
	{
		ret.push_back(x % 512);
		x /= 512;
	}
	return ret;
}
mt19937_64 gen(123123);
ll H[512];
ll get(ll x)
{
	ll ret = 0;
	for (int i = 0; i < k; i++)
	{
		ret ^= H[x % 512];
		x /= 512;
	}
	return ret;
}
bool blogai(ll a, int x)
{
	int plius = 0;
	for (int i = 0; i < k; i++)
	{
		if ((a % 512) == x)
			plius++;
		a /= 512;
	}
	return plius == 1;
}
const int dydis = 150000000;
bitset<dydis>M;
int main()
{
	srand(clock());
	for (int i = 0; i < 512; i++)
	{
		H[i] = gen();
	}
	ios_base::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k >> kth;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < k; j++)
		{
			cin >> a[i][j];
		}
	}
	vector<int>best;
	{
		for (int j = 0; j < k; j++)
		{
			pair<int, int>mx = { -1, -1};
			for (int i = 0; i < n; i++)
			{
				mx = max(mx, {a[i][j], i});
			}
			if (find(best.begin(), best.end(), mx.second) == best.end())
				best.push_back(mx.second);
		}
	}
	while ((int)best.size() < k)
	{
		int x = rand() % n;
		if (find(best.begin(), best.end(), x) == best.end())
			best.push_back(x);
	}
	set<pair<int, ll>>Q;
	ll xx = convert(best);
	Q.insert({value(xx), xx});
	M[abs(get(xx) % dydis)] = true;
	while (!Q.empty())
	{
		auto it = --Q.end();
		ll aa = it->second;
		int vall = it->first;
		Q.erase(it);
		if (kth == 1)
		{
			cout << vall << "\n";
			return 0;
		}
		kth--;
		ll hh = get(aa);
		int mini = Q.begin()->first;
		for (int t = 0; t < n; t++)
		{
			ll tt = t;
			ll w = 511;
			ll hh1 = hh ^ H[t];
			ll aaa = aa;
			for (int i = 0; i < k; i++)
			{
				ll bb = ((aa & (~w)) | tt);
				ll hh2 = hh1 ^ H[aaa % 512];
				if (blogai(bb, t))
				{
					if (M[abs(hh2 % dydis)] == false)
					{
						int gal = value(bb);
						bool ok = true;
						if ((int)Q.size() >= 2000)
						{
							if (gal <= mini)
								ok = false;
						}
						if (ok)
						{
							M[abs(hh2 % dydis)] = true;
							Q.insert({gal, bb});
							mini = min(mini, gal);
						}
					}
					w *= 512;
					tt *= 512;
					aaa /= 512;
				}
			}
		}
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32