Submission #604101

#	Time	Username	Problem	Language	Result	Execution time	Memory
604101		Tigryonochekk	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	456 ms	51340 KiB

tickets

#include <iostream>
#include <algorithm>
#include "tickets.h"
#include <vector>
#define ll long long
using namespace std;
const ll inf = 1e18 + 69;
#define pii pair<int, int>

vector<vector<int>> answer;
ll ans;

vector<pii> wtf[1502];

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	answer.resize(n);
	for (int i = 0; i < n; i++) {
		answer[i].resize(m, -1);
	}
	if (k == 1) {
		vector<pii> d(n);
		for (int i = 0; i < n; i++) {
			d[i] = pii(x[i][m - 1] + x[i][0], i);
			ans += x[i][m - 1];
		}
		sort(d.begin(), d.end());
		vector<int> v(n);
		for (int i = 0; i < n / 2; i++) {
			int ind = d[i].second;
			answer[ind][0] = 0;
			ans -= d[i].first;
		}
		for (int i = n / 2; i < n; i++) {
			int ind = d[i].second;
			answer[ind][m - 1] = 0;
		}
	}
	else if (k == m) {
		vector<pii> all;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				all.push_back(pii(x[i][j], i * m + j));
			}
		}
		sort(all.begin(), all.end());
		for (int i = n * m / 2; i < n * m; i++) {
			ans += all[i].first;
		}
		for (int i = 0; i < n * m / 2; i++) {
			ans -= all[i].first;
		}
		pii mid = all[n + m / 2];
		vector<int> ty(n); // -1 ++, -2 --, tver@ +- u vortex a sksvum +
		int a = 0, b = 0;
		vector<int> pm;
		
		for (int i = 0; i < n; i++) {
			if (pii(x[i][0], i * m) >= mid) {
				ty[i] = -1;
				a++;
			}
			else if (pii(x[i][m - 1], i * m + m - 1) < mid) {
				ty[i] = -2;
				b++;
			}
			else {
				for (int j = 0; j < m; j++) {
					wtf[i].push_back(pii(x[i][j], i * m + j));
				}
				ty[i] = lower_bound(wtf[i].begin(), wtf[i].end(), mid) - wtf[i].begin();
				pm.push_back(i);
			}
		}
		for (int i = 0; i < n; i++) {
			if (ty[i] < 0) {
				for (int j = 0; j < m; j++) {
					answer[i][j] = j;
				}
			}
		}
		vector<int> zn(n), zv(n);
		fill(zv.begin(), zv.end(), m - 1);
		for (int j = 0; j < m; j++) {
			int aa = n / 2 - a, bb = n / 2 - b;
			for (int i = 0; i < n; i++) {
				if (ty[i] < 0) continue;
				if (zn[i] <= ty[i] && aa) {
					answer[i][zn[i]] = j;
					zn[i]++;
					aa--;
				}
				else {
					answer[i][zv[i]] = j;
					zv[i]--;
					bb--;
				}
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

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