Submission #300302

#	Time	Username	Problem	Language	Result	Execution time	Memory
300302		ecnerwala	Carnival Tickets (IOI20_tickets)	C++17	41 / 100	1100 ms	106360 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

long long find_maximum(int K, std::vector<std::vector<int>> X) {
	int N = int(X.size());
	int M = int(X[0].size());

	std::vector<std::vector<int>> answer(N, std::vector<int>(M, -1));
	struct cnd_t {
		std::pair<int, int> val;
		int i;
		int j0, j1;
	};

	std::vector<cnd_t> cnds; cnds.reserve(N*K);

	int64_t tot_val = 0;
	{
		std::vector<std::pair<int, int>> vals(M);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				vals[j] = {X[i][j], j};
			}
			std::sort(vals.begin(), vals.end(), [&](const auto& a, const auto& b) { return a.first < b.first; });
			for (int j = 0; j < K; j++) {
				tot_val -= vals[j].first;
				answer[i][vals[j].second] = -3;
				cnds.push_back({{vals[j].first + vals[j+(M-K)].first, j}, i, vals[j].second, vals[j+(M-K)].second});
			}
		}
	}
	auto md = cnds.begin() + N/2*K;
	std::nth_element(cnds.begin(), md, cnds.end(),
			[&](const auto& a, const auto& b) { return a.val > b.val; });
	cnds.erase(md, cnds.end());
	for (auto [v, i, j0, j1] : cnds) {
		tot_val += v.first;
		assert(answer[i][j0] == -3);
		answer[i][j0] = -1;
		assert(answer[i][j1] == -1);
		answer[i][j1] = -2;
	}
	std::cerr << "tot_val = " << tot_val << '\n';

	std::vector<std::array<std::vector<int>, 2>> ticks(N);
	for (int i = 0; i < N; i++) {
		ticks[i][0].reserve(K);
		ticks[i][1].reserve(K);
		for (int j = 0; j < M; j++) {
			if (answer[i][j] == -3) ticks[i][0].push_back(j);
			else if (answer[i][j] == -2) ticks[i][1].push_back(j);
			else if (answer[i][j] == -1);
			else assert(false);
		}
		assert(int(ticks[i][0].size()) + int(ticks[i][1].size()) == K);
	}

	for (int k = 0; k < K; k++) {
		int c0 = 0;
		int c1 = 0;
		for (int i = 0; i < N; i++) {
			if (ticks[i][0].empty()) {
				c1++;
			} else if (ticks[i][1].empty()) {
				c0++;
			} else {
				// do nothing
			}
		}
		assert(c0 <= N/2 && c1 <= N/2);
		for (int i = 0; i < N; i++) {
			int d;
			if (ticks[i][0].empty()) {
				d = 1;
			} else if (ticks[i][1].empty()) {
				d = 0;
			} else if (c0 < N/2) {
				c0++;
				d = 0;
			} else if (c1 < N/2) {
				c1++;
				d = 1;
			} else assert(false);
			answer[i][ticks[i][d].back()] = k;
			ticks[i][d].pop_back();
		}
	}

	allocate_tickets(answer);
	return tot_val;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10