Submission #824954

#	Time	Username	Problem	Language	Result	Execution time	Memory
824954		pedroslrey	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	852 ms	79332 KiB

tickets

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

using namespace std;
using lli = long long;

vector<vector<int>> calc(vector<stack<int>> plus, vector<stack<int>> minus, int m, int k) {
	int n = plus.size();

	vector<vector<int>> ans(n, vector<int>(m, -1));
	for (int round = 0; round < k; ++round) {
		int cntplus = 0, cntminus = 0;
		auto add_plus = [&plus, &ans, &round, &cntplus](int i) {
			ans[i][plus[i].top()] = round;
			plus[i].pop();
			++cntplus;
		};

		auto add_minus = [&minus, &ans, &round, &cntminus](int i) {
			ans[i][minus[i].top()] = round;
			minus[i].pop();
			++cntminus;
		};

		// cerr << "BEGIN\n";
		for (int i = 0; i < n; ++i) {
			// cerr << plus[i].size() << " " << minus[i].size() << "\n";
			if (plus[i].empty()) add_minus(i);
			else if (minus[i].empty()) add_plus(i);
		}
		for (int i = 0; i < n; ++i)
			if (!plus[i].empty() && !minus[i].empty())
				if (cntplus > cntminus) add_minus(i);
				else add_plus(i);
		// cerr << "END " << cntplus << " " << cntminus << "\n";
	}

	return ans;
}

lli val(vector<vector<int>> &ans, vector<vector<int>> &ms, int k) {
	int n = ans.size(), m = ans[0].size();

	vector<vector<int>> rounds(k);
	for (int i = 0; i < n; ++i) 
		for (int j = 0; j < m; ++j) 
			if (ans[i][j] != -1) rounds[ans[i][j]].push_back(ms[i][j]);

	lli sum = 0;
	for (int r = 0; r < k; ++r) {
		sort(rounds[r].begin(), rounds[r].end());

		for (int i = 0; i < n/2; ++i)
			sum -= rounds[r][i];
		for (int i = n/2; i < n; ++i)
			sum += rounds[r][i];
	}

	return sum;
}

lli find_maximum(int k, vector<vector<int>> ms) {
	int n = ms.size(), m = ms[0].size();

	vector<vector<int>> ids(n, vector<int>(m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j)
			ids[i][j] = j;

		sort(ids[i].begin(), ids[i].end(), [&](int a, int b) { return ms[i][a] < ms[i][b]; });
	}

	vector<int> stage(n, 0);
	set<pair<lli, int>> increase;

	auto add = [&](int i) {
		int x = stage[i]; auto &id = ids[i];
		increase.emplace(ms[i][id[k-1-x]] + ms[i][id[m-1-x]], i);
	};

	for (int i = 0; i < n; ++i)
		add(i);

	for (int i = 0; i < n*k/2; ++i) {
		auto [x, idx] = *increase.rbegin(); increase.erase(--increase.end());
		
		++stage[idx];
		if (stage[idx] < k) add(idx);
	}

	vector<stack<int>> plus(n), minus(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < k - stage[i]; ++j)
			minus[i].push(ids[i][j]);
		for (int j = m-1; j >= m - stage[i]; --j)
			plus[i].push(ids[i][j]);
	}

	auto ans = calc(plus, minus, m, k);
	allocate_tickets(ans);

	return val(ans, ms, k);
}

Compilation message (stderr)

tickets.cpp: In function 'std::vector<std::vector<int> > calc(std::vector<std::stack<int> >, std::vector<std::stack<int> >, int, int)':
tickets.cpp:32:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   32 |    if (!plus[i].empty() && !minus[i].empty())
      |       ^
tickets.cpp: In function 'lli find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:85:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |   auto [x, idx] = *increase.rbegin(); increase.erase(--increase.end());
      |        ^

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