Submission #465384

#	Time	Username	Problem	Language	Result	Execution time	Memory
465384		armand	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	644 ms	55868 KiB

tickets

#include "tickets.h"
#include <vector>
#include <algorithm>
using namespace std;

bool is01(std::vector<std::vector<int>> x)
{
	int n = x.size();
	int m = x[0].size();
	int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (x[i][j] > 1)
				return false;
	return true;
}

long long find_maximum(int k, std::vector<std::vector<int>> x)
{
	int n = x.size();
	int m = x[0].size();
	int i, j;
	long long res = 0;
	std::vector<std::vector<int>> answer;
	for (i = 0; i < n; i++) {
		std::vector<int> row(m, -1);
		answer.push_back(row);
	}
	if (is01(x)) {
		vector<int> n1(n, 0), n0(n, 0);
		vector<int> ones[1505], zeros[1505];
		for (i = 0; i < n; i++) {
			for (j = 0; j < m; j++) {
				n1[i] += x[i][j];
				if (x[i][j] == 1)
					ones[i].push_back(j);
				else
					zeros[i].push_back(j);
			}
			n0[i] = n - n1[i];
		}
		while (k--) {
			vector< pair<int, int> > p1;
			for (i = 0; i < n; i++)
				p1.push_back(make_pair(n1[i], i));
			sort(p1.begin(), p1.end());
			int can_produce_one = 0, can_produce_zero = 0;
			for (i = 0; i < n; i++) {
				if (n1[i]) can_produce_one++;
				if (n0[i]) can_produce_zero++;
			}
			int zero = n / 2, one = n / 2;
			if (can_produce_zero < n / 2) {
				zero = can_produce_zero;
				one = n - can_produce_zero;
			}
			if (can_produce_one < n / 2) {
				zero = n - can_produce_one;
				one = can_produce_one;
			}
			for (j = 0; j < zero; j++) {
				int company = p1[j].second;
				answer[company][zeros[company].back()] = k;
				zeros[company].pop_back();
				n0[company]--;
			}
			for (j = 0; j < one; j++) {
				int company = p1[n - j - 1].second;
				answer[company][ones[company].back()] = k;
				ones[company].pop_back();
				n1[company]--;
				res++;
			}

		}
		allocate_tickets(answer);
		if (res > k*n / 2)
			res = k * n - res;
		return res;
	}
	vector<pair<int, int> > a(n);
	vector<int> min_index(n), max_index(n);
	for (i = 0; i < n; i++) {
		min_index[i] = 0;
		max_index[i] = m-1;
	}
	for (i = 0; i < n; i++) {
		a[i].first = x[i][max_index[i]] + x[i][min_index[i]];
		a[i].second = i;
		res -= x[i][min_index[i]];
	}
	sort(a.begin(), a.end());
	for (i = 0; i < n / 2; i++)
		answer[a[i].second][min_index[a[i].second]] = 0;
	for (i = n / 2; i < n; i++) {
		answer[a[i].second][max_index[a[i].second]] = 0;
		res += a[i].first;
	}
	allocate_tickets(answer);
	return res;
}

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