Submission #316163

#	Time	Username	Problem	Language	Result	Execution time	Memory
316163		srvlt	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	2 ms	768 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) (int)(x).size()
#define all(x) begin(x), end(x)
using namespace std;

int n, m;
set <array <int, 3>> st;
vector <vector <int>> a, ans;
vector <int> l, r;
ll res;

void erase(int x, int y) {
	st.erase({a[x][y], x, y});
	if (l[x] == y) st.erase({a[x][r[x]], x, r[x]}), l[x]++;
	else st.erase({a[x][l[x]], x, l[x]}), r[x]--;
}

void connect(int i, array <int, 3> & x, array <int, 3> & y) {
	//cerr << "res += |" << x[0] << " - " << y[0] << "|\n";
	res += abs(x[0] - y[0]);
	int A = x[1], B = x[2];
	int C = y[1], D = y[2];
	ans[A][B] = ans[C][D] = i;
	erase(A, B), erase(C, D);
}

ll find_maximum(int k, vector<vector<int>> A) {
	st.clear(), ans.clear();
	n = A.size(), m = A[0].size(), a = A;
	l = vector <int>(n, 0), r = vector <int>(n, m - 1);
	res = 0;
	for (int i = 0; i < n; i++)
		ans.push_back(vector <int>(m, -1));
	for (int it = 0; it < k; it++) {
		st.clear();
		for (int i = 0; i < n; i++) {
			int L = l[i], R = r[i];
			if (L > R) continue;
			st.insert({a[i][L], i, L});
			if (L != R)
				st.insert({a[i][R], i, R});
		}
		while (SZ(st) > 1) {
			auto x = *begin(st), y = *(--end(st));
			if (x[1] == y[1]) {
				assert(SZ(st) > 2);
				auto x2 = *(++begin(st)), y2 = *(prev(--end(st)));
				if (abs(x[0] - y2[0]) > abs(x2[0] - y[0]))
					connect(it, x, y2);
				else
					connect(it, x2, y);
			}	else connect(it, x, y);
		}
	}
	allocate_tickets(ans);
	return res;
}

• 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