Submission #612220

#	Time	Username	Problem	Language	Result	Execution time	Memory
612220		DanShaders	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1670 ms	120472 KiB

tickets

//Cgrader.cpp
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
using ll = long long;
using ld = long double;
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())

const int N = 2100;

vector<int> pw[2][N];
vector<int> sorted[N];

ll find_maximum(int k, vector<vector<int>> d) {
	int n = sz(d), m = sz(d[0]);

	vector<tuple<int, int, int>> a;
	for (int i = 0; i < n; ++i) {
		sorted[i] = vector(m, 0);
		iota(all(sorted[i]), 0);
		sort(all(sorted[i]), [&](int x, int y) {
			return tie(d[i][x], x) < tie(d[i][y], y);
		});
		for (int j = 0; j < m; ++j) {
			a.push_back({d[i][j], i, j});
		}
	}	
	stable_sort(all(a));

	ll ans = 0;

	for (int i = 0; i < n * m; ++i) {
		auto [val, x, y] = a[i];
		if (sz(pw[0][x]) < k) {
			ans -= val;
			pw[0][x].push_back(y);
		}
	}

	set<pair<int, int>> cands;
	for (int j = 0; j < n; ++j) {
		if (!sz(pw[0][j])) {
			continue;
		}
		int cval = d[j][sorted[j][m - sz(pw[1][j]) - 1]] + d[j][pw[0][j].back()];
		cands.insert({cval, j});
	}

	for (int i = 0; i < n * k / 2; ++i) {
		auto [value, j] = *cands.rbegin();
		ans += value;

		pw[1][j].push_back(sorted[j][m - sz(pw[1][j]) - 1]);
		pw[0][j].pop_back();

		cands.erase(--cands.end());

		if (sz(pw[0][j])) {
			int cval = d[j][sorted[j][m - sz(pw[1][j]) - 1]] + d[j][pw[0][j].back()];
			cands.insert({cval, j});
		}
	}

	// int sz0 = 0, sz1 = 0;
	// for (int i = 0; i < n; ++i) {
	// 	vector<int> indexes = pw[0][i];
	// 	indexes.insert(end(indexes), all(pw[1][i]));
	// 	sort(all(indexes));
	// 	assert(unique(all(indexes)) == end(indexes));
	// 	assert(sz(pw[0][i]) + sz(pw[1][i]) == k);
	// 	sz0 += sz(pw[0][i]);
	// 	sz1 += sz(pw[1][i]);
	// }
	// assert(sz0 == n * k / 2 && sz1 == n * k / 2);

	set<pair<int, int>> where;
	for (int i = 0; i < n; ++i) {
		where.insert({sz(pw[0][i]), i});
	}

	vector s(n, vector(m, -1));

	for (int i = 0; i < k; ++i) {
		set<pair<int, int>> nwhere;
		
		auto it = where.begin();
		for (int j = 0; j < n; ++j, ++it) {
			auto [val, x] = *it;
			if (2 * j >= n) {
				s[x][pw[0][x].back()] = i;
				pw[0][x].pop_back();
				nwhere.insert({val - 1, x});
			} else {
				s[x][pw[1][x].back()] = i;
				pw[1][x].pop_back();
				nwhere.insert({val, x});
			}
		}
		where = nwhere;
	}

	// vector<int> good(m, -1);
	// iota(end(good) - k, end(good), 0);
	// for (int i = 0; i < n; ++i) {
	// 	auto c = s[i];
	// 	sort(all(c));
	// 	assert(good == c);
	// }
	allocate_tickets(s);
	return ans;	
}

• 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