oj.uz

답안 #128356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128356 2019-07-10T19:01:12 Z tutis Olympiads (BOI19_olympiads) C++17
44 / 100
 2000 ms 131244 KB 
/*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.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 21624 KB Output is correct
2 Correct 178 ms 25008 KB Output is correct
3 Correct 239 ms 24952 KB Output is correct
4 Correct 86 ms 11128 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 23716 KB Output is correct
2 Correct 79 ms 22052 KB Output is correct
3 Correct 65 ms 15472 KB Output is correct
4 Correct 68 ms 18936 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2023 ms 131244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 21624 KB Output is correct
2 Correct 178 ms 25008 KB Output is correct
3 Correct 239 ms 24952 KB Output is correct
4 Correct 86 ms 11128 KB Output is correct
5 Correct 116 ms 23716 KB Output is correct
6 Correct 79 ms 22052 KB Output is correct
7 Correct 65 ms 15472 KB Output is correct
8 Correct 68 ms 18936 KB Output is correct
9 Execution timed out 2023 ms 131244 KB Time limit exceeded
10 Halted 0 ms 0 KB -