Submission #542209

#	Time	Username	Problem	Language	Result	Execution time	Memory
542209		LucaDantas	Carnival Tickets (IOI20_tickets)	C++17	55 / 100	797 ms	84200 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();

	if(k == 1) {
		long long ans = 0;
		vector<vector<int>> build(n, vector<int>(m, -1));

		for(int i = 0; i < n; i++)
			ans -= x[i][0], build[i][0] = 0;

		vector<pair<int,int>> opt;
		for(int i = 0; i < n; i++)
			opt.push_back({x[i].back() + x[i].front(), i});
		sort(opt.begin(), opt.end(), greater<pair<int,int>>());
		
		for(int i = 0; i < n/2; i++)
			build[opt[i].second].front() = -1, build[opt[i].second].back() = 0, ans += opt[i].first;

		allocate_tickets(build);
		return ans;
	}

	if(k == m) {
		long long ans = 0;
		vector<pair<int,pair<int,int>>> all;
		vector<vector<int>> build(n, vector<int>(m, -1));

		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				all.push_back({x[i][j], {i, j}});
		sort(all.begin(), all.end());
		
		vector<vector<int>> rm(n), add(n);
		
		for(int i = 0; i < n*m/2; i++)
			rm[all[i].second.first].push_back(all[i].second.second), ans -= all[i].first;
		
		for(int i = n*m/2; i < n*m; i++)
			add[all[i].second.first].push_back(all[i].second.second), ans += all[i].first;
		
		vector<vector<bool>> mark(n, vector<bool>(m));
		int index = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < (int)rm[i].size(); j++, index = (index+1)%k)
				build[i][rm[i][j]] = index, mark[i][index] = 1;
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < (int)add[i].size(); j++, index = (index+1)%k) {
				while(mark[i][index]) index = (index + 1) % k;
				build[i][add[i][j]] = index;
				mark[i][index] = 1;
			}
		}

		allocate_tickets(build);
		return ans;
	}

	int mx = 0;
	for(auto vetor : x)
		for(int sla : vetor)
			mx = max(mx, sla);

	if(mx <= 1) {
		vector<vector<int>> build(n, vector<int>(m, -1));
		
		vector<pair<int,pair<vector<int>, vector<int>>>> pares;

		for(int i = 0; i < n; i++) {
			vector<int> p, n;
			for(int j = 0; j < m; j++)
				if(x[i][j]) p.push_back(j);
				else n.push_back(j);
			pares.push_back({i, {p, n}});
		}

		for(int round = 0; round < k; round++) {
			sort(pares.begin(), pares.end(), [](const auto& a, const auto& b) { return a.second.first.size() > b.second.first.size(); });

			for(int i = 0; i < n/2; i++) {
				int id = pares[i].first;
				bool swp = 0;
				if(!pares[i].second.first.size()) swp = 1;
				
				if(swp) swap(pares[i].second.first, pares[i].second.second);
				
				build[id][pares[i].second.first.back()] = round;
				pares[i].second.first.pop_back();

				if(swp) swap(pares[i].second.first, pares[i].second.second);
			}

			for(int i = n/2; i < n; i++) {
				swap(pares[i].second.first, pares[i].second.second);

				int id = pares[i].first;
				bool swp = 0;
				if(!pares[i].second.first.size()) swp = 1;
				
				if(swp) swap(pares[i].second.first, pares[i].second.second);
				
				build[id][pares[i].second.first.back()] = round;
				pares[i].second.first.pop_back();

				if(swp) swap(pares[i].second.first, pares[i].second.second);

				swap(pares[i].second.first, pares[i].second.second);
			}
		}

		int soma = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				if(build[i][j] != -1) soma += x[i][j];

		allocate_tickets(build);
		return min(soma, k*n - soma);
	}

	return 0;
}

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