Submission #303035

#	Time	Username	Problem	Language	Result	Execution time	Memory
303035		tutis	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	3078 ms	27000 KiB

tickets

#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<int>> answer(n, vector<int>(m, -1));
	int a[n], b[n];
	for (int i = 0; i < n; i++)
	{
		a[i] = 0;
		b[i] = m - 1;
	}
	long long ret = 0;
	for (int g = 0; g < k; g++)
	{
		vector<int>vals;
		for (int i = 0; i < n; i++)
			vals.push_back(x[i][a[i]]);
		sort(vals.begin(), vals.end());
		multiset<int>A, B;
		for (int i = 0; i < n / 2; i++)
			A.insert(vals[i]);
		for (int i = n / 2; i < n; i++)
			B.insert(vals[i]);
		bool koks[n];
		for (int i = 0; i < n; i++)
			koks[i] = false;
		bool ok = true;
		auto add = [&](long long v)
		{
			if (v < *B.begin())
			{
				A.insert(v);
				return -v;
			}
			else
			{
				B.insert(v);
				return v;
			}
		};
		auto eras = [&](int v)
		{
			long long ret = 0;
			if (A.find(v) != A.end())
			{
				A.erase(A.find(v));
				ret += v;
			}
			else
			{
				B.erase(B.find(v));
				ret -= v;
			}
			while (A.size() < B.size())
			{
				auto it = B.begin();
				int x = *it;
				B.erase(it);
				A.insert(x);
				ret -= x * 2;
			}
			while (A.size() > B.size())
			{
				auto it = --A.end();
				int x = *it;
				A.erase(it);
				B.insert(x);
				ret += x * 2;
			}
			return ret;
		};
		while (ok)
		{
			ok = false;
			for (int i = 0; i < n; i++)
			{
				int v1 = x[i][a[i]];
				int v2 = x[i][b[i]];
				if (koks[i])
					swap(v1, v2);
				if (add(v2) + eras(v1) > 0)
				{
					koks[i] = !koks[i];
					ok = true;
				}
				else
				{
					add(v1);
					eras(v2);
				}
			}
			for (int i = 0; i < n; i++)
			{
				int v1 = x[i][a[i]];
				int v2 = x[i][b[i]];
				if (koks[i])
					swap(v1, v2);
				for (int j = 0; j < i; j++)
				{
					int w1 = x[j][a[j]];
					int w2 = x[j][b[j]];
					if (koks[j])
						swap(w1, w2);
					if (add(v2) + eras(v1) + add(w2) + eras(w1) > 0)
					{
						koks[i] = !koks[i];
						koks[j] = !koks[j];
						ok = true;
						break;
					}
					else
					{
						add(v1);
						eras(v2);
						add(w1);
						eras(w2);
					}
				}
			}
		}
		for (int i = 0; i < n; i++)
			if (koks[i])
			{
				answer[i][b[i]] = g;
				b[i]--;
			}
			else
			{
				answer[i][a[i]] = g;
				a[i]++;
			}
		for (int i : A)
			ret -= i;
		for (int i : B)
			ret += i;
	}
	allocate_tickets(answer);
	return ret;
}

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