Submission #612079

#	Time	Username	Problem	Language	Result	Execution time	Memory
612079		DanShaders	Carnival Tickets (IOI20_tickets)	C++17	25 / 100	1148 ms	85700 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 = 1600;

vector<int> pw[2][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) {
		for (int j = 0; j < m; ++j) {
			a.push_back({d[i][j], i, j});
		}
	}
	sort(all(a));

	ll ans = 0;
	int required = n * k / 2;
	for (int i = 0; required; ++i) {
		auto [value, x, y] = a[i];
		if (sz(pw[0][x]) < k) {
			ans -= value;
			pw[0][x].push_back(y);
			--required;
		}
	}
	required = n * k / 2;
	for (int i = n * m; i-- && required; ) {
		auto [value, x, y] = a[i];
		if (sz(pw[0][x]) < k) {
			ans += value;
			pw[1][x].push_back(y);
			--required;
		}
	}

	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;
	}
	allocate_tickets(s);
	return ans;
}

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