Submission #421360

#	Time	Username	Problem	Language	Result	Execution time	Memory
421360		Mazaalai	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	3 ms	972 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PII;
#define ff first
#define ss second
 
long long find_maximum(int k1, vector <vector <int> > x1) {
	ll n = x1.size();
	ll m = x1[0].size();
	ll k = k1;
	vector <vector <int> > answer(n, vector <int>(m, -1));
	vector <vector <bool> > state(n, vector <bool>(m, 0));
	vector <vector <ll> > x(n, vector<ll>(m));
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++) x[i][j] = x1[i][j];
	vector <ll> hiIdx(n+5, m-1), used(n+5, 0);
	vector <ll> loIdx(n+5, 0);
	set <PII> hiVal, loVal; // val, idx;
	for (ll i = 0; i < n; i++) {
		hiVal.insert({-x[i][hiIdx[i]], i});
		loVal.insert({x[i][loIdx[i]], i});
	}
	ll cnt = 0, ans = 0;
	vector <vector <PII> > pairs;
	while(cnt < n) {
		while(!hiVal.empty() && used[(hiVal.begin())->ss] >= k) 
			hiVal.erase(hiVal.begin());
		while(!loVal.empty() && used[(loVal.begin())->ss] >= k) 
			loVal.erase(loVal.begin());
		auto itMax = hiVal.begin();
		auto itMin = loVal.begin();
		PII maxi = *itMax;
		PII mini = *itMin;
		ll a, b;
		a = maxi.ss;
		b = mini.ss;
		if (a == b && used[a] == k - 1) {
			while(hiVal.size() > 1 && used[(++hiVal.begin())->ss] >= k) 
				hiVal.erase(hiVal.begin());
			while(loVal.size() > 1 && used[(++loVal.begin())->ss] >= k) 
				loVal.erase(loVal.begin());
			auto itMax1 = (++hiVal.begin());
			auto itMin1 = (++loVal.begin());
			PII maxi1 = *itMax1;
			PII mini1 = *itMin1;
			ll a1, b1;
			a1 = maxi1.ss;
			b1 = mini1.ss;
			ll dif1 = abs(x[a][hiIdx[a]] - x[b1][loIdx[b1]]);
			ll dif2 = abs(x[a1][hiIdx[a1]] - x[b][loIdx[b]]);
			if (dif1 > dif2) {
				b = b1;
				itMin = itMin1;
			} else {
				a = a1;
				itMax = itMax1;
			}
		}
		hiVal.erase(itMax);
		loVal.erase(itMin);
		ll dif = abs(x[a][hiIdx[a]] - x[b][loIdx[b]]);
		ans += dif;
		maxi = {a, hiIdx[a]};
		mini = {b, loIdx[b]};
		state[a][hiIdx[a]] = state[b][loIdx[b]] = 1;
		hiVal.insert({-x[a][--hiIdx[a]], a});
		loVal.insert({x[b][++loIdx[b]], b});
		used[a]++;
		used[b]++;
		cnt += (used[a] == k);
		if (a != b) cnt += (used[b] == k);

		// cout << "--------\n";
		// for (int i = 0; i < n; i++) {
		// 	for (int j = 0; j < m; j++) {
		// 		cout << state[i][j] << ' ';
		// 	}
		// 	cout << '\n';
		// }
	}
	for (int i = 0; i < n; i++) {
		int cur = 0;
		for (int j = 0; j < m; j++) {
			// cout << state[i][j] << ' ';
			if (state[i][j]) answer[i][j] = cur++;
		}
		// cout << '\n';
	}
	allocate_tickets(answer);
	return ans;
}

• 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