제출 #420664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420664		Mazaalai	카니발 티켓 (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 k, vector <vector <int> > x) {
	ll n = x.size();
	ll m = x[0].size();
	vector <vector <int> > answer(n, vector <int>(m, -1));
	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-1) {
		// max1, max2, min1, min2
		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 itMax1 = hiVal.begin();
		auto itMin1 = loVal.begin();
		PII max1 = *itMax1, max2;
		PII min1 = *itMin1, min2;
		ll a, b;
		if (max1.ss != min1.ss) {
			a = max1.ss;
			b = min1.ss;
			hiVal.erase(max1);
			loVal.erase(min1);
		} else {
			while(!hiVal.empty() && used[(++hiVal.begin())->ss] >= k) 
				hiVal.erase(++hiVal.begin());
			while(!loVal.empty() && used[(++loVal.begin())->ss] >= k) 
				loVal.erase(++loVal.begin());
			max2 = *(++itMax1);
			min2 = *(++itMin1);
			if (-max1.ff - min2.ff >= -max2.ff - min1.ff) {
				a = max1.ss;
				b = min2.ss;
				hiVal.erase(max1);
				loVal.erase(min2);
			} else {
				a = max2.ss;
				b = min1.ss;
				hiVal.erase(max2);
				loVal.erase(min1);
			}
		}
		ll dif = abs(x[a][hiIdx[a]] - x[b][loIdx[b]]);
		max1 = {a, hiIdx[a]};
		min1 = {b, loIdx[b]};
		pairs.push_back({max1, min1});
		ans += dif;
		hiVal.insert({-x[a][--hiIdx[a]], a});
		loVal.insert({x[b][++loIdx[b]], b});
		// cout << a << ' ' << b << '\n';
		used[a]++;
		used[b]++;
		cnt += (used[a] == k);
		cnt += (used[b] == k);
	}
	// cout << "DONE\n";
	if (cnt == n - 1) {
		vector <vector <PII> > tmp;
		int idx = 0;
		while(used[idx] == k) idx++;
		while(used[idx] < k) {
			vector <PII> temp = pairs.back();
			pairs.pop_back();
			if (temp[0].ff == idx || temp[1].ff == idx) {
				tmp.push_back(temp);
				continue;
			}
			PII cur = {hiIdx[idx], loIdx[idx]};
			PII cur1 = {idx, loIdx[idx]++};
			PII cur2 = {idx, hiIdx[idx]--};
			int a2, a1, b2, b1, c1 = idx, c2, c3;
			tie(a1, a2) = temp[0];
			tie(b1, b2) = temp[1];
			tie(c2, c3) = cur;
			// cout << "REM:" << a1 << ' ' << b1 << '\n';
			// cout << "ADD:" << a1 << ' ' << c1 << '\n';
			// cout << "ADD:" << b1 << ' ' << c1 << '\n';
			ans -= abs(x[a1][a2] - x[b1][b2]);
			ans += abs(x[a1][a2] - x[c1][c3]);
			ans += abs(x[b1][b2] - x[c1][c2]);
			tmp.push_back({temp[0], cur1});
			tmp.push_back({cur2, temp[1]});
			used[idx] += 2;
		}
		for (auto el : tmp) pairs.push_back(el);
	}
	// cout << "DONE1\n";
	vector <set <ll> > pickSets(n);
	for (ll i = 0; i < n; i++) 
	for (ll j = 0; j < k; j++) pickSets[i].insert(j);
	for (auto el : pairs) {
		ll a1, a2, b1, b2;
		tie(a1, a2) = el[0];
		tie(b1, b2) = el[1];
		for (auto pos : pickSets[a1]) {
			auto it = pickSets[b1].lower_bound(pos);
			if (it == pickSets[b1].end() || *it != pos) continue;
			pickSets[a1].erase(pos);
			pickSets[b1].erase(pos);
			answer[a1][a2] = answer[b1][b2] = pos;
			// cout << "ADD\n";
			break;
		}
	}
 
	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