제출 #361341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361341		tutis	Olympiads (BOI19_olympiads)	C++17	0 / 100	17 ms	2288 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
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using ordered_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using fast_map = cc_hash_table<T, X>;
//using ull = __uint128_t;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
mt19937_64 rng(123);
const ll mod = 1000000007;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k, c;
	cin >> n >> k >> c;
	vector<vector<int>> A(n, vector<int>(k));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < k; j++)
			cin >> A[i][j];
	vector<vector<int>> p(k, vector<int>(n));
	vector<vector<int>> q(k, vector<int>(n));
	for (int i = 0; i < k; i++)
	{
		iota(p[i].begin(), p[i].end(), 0);
		sort(p[i].begin(), p[i].end(), [&](int x, int y) {return A[x][i] > A[y][i];});
		for (int j = 0; j < n; j++)
			q[i][p[i][j]] = j;
	}
	vector<ull>H(n);
	for (int i = 0; i < n; i++)
		H[i] = rng();
	auto f = [&](const array<int, 6>&v)->ull
	{
		ll r = 0;
		for (int i = 0; i < k; i++)
			r ^= H[v[i]];
		return r;
	};
	auto eval = [&](const array<int, 6>&v)->int
	{
		int ret = 0;
		for (int i = 0; i < k; i++)
		{
			int mx = 0;
			for (int j = 0; j < k; j++)
				mx = max(mx, A[v[j]][i]);
			ret += mx;
		}
		return ret;
	};
	priority_queue<pair<int, array<int, 6>>>Q;
	{
		set<int>a;
		for (int i = 0; i < k; i++)
			a.insert(p[i][0]);
		while (a.size() < k)
			a.insert(rng() % k);
		array<int, 6>s;
		int t = 0;
		for (int v : a)
			s[t++] = v;
		Q.push({eval(s), s});
	}
	set<ull>BUV;
	while (!Q.empty())
	{
		int sum = Q.top().first;
		array<int, 6>v = Q.top().second;
		Q.pop();
		ull h = f(v);
		if (BUV.count(h))
			continue;
		BUV.insert(h);
		c--;
		if (c == 0)
		{
			cout << sum << "\n";
			return 0;
		}
		for (int a = 0; a < k; a++)
		{
			int j = 0;
			for (int jj = 1; jj < k; jj++)
				if (q[a][v[jj]] > q[a][v[j]])
					j = jj;
			for (int i = 0; i < k; i++)
			{
				int c = q[a][v[j]];
				if (c != n - 1)
				{
					int buvo = v[i];
					v[i] = p[a][c + 1];
					bool ok = true;
					for (int c = 0; c < k; c++)
						if (i != c && v[i] == v[c])
							ok = false;
					if (ok)
						Q.push({eval(v), v});
					v[i] = buvo;
				}
			}
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

olympiads.cpp: In function 'int main()':
olympiads.cpp:74:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |   while (a.size() < k)
      |          ~~~~~~~~~^~~

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