Submission #823306

#	Time	Username	Problem	Language	Result	Execution time	Memory
823306		Sohsoh84	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1287 ms	123596 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1500 + 10;

vector<int> mn_vec[MAXN], mx_vec[MAXN];
ll fans = 0, tt, n, m, len[MAXN];
vector<vector<int>> res, A;
bool flag[MAXN]; 
int k;

inline void get() {
	int cnt_mx = n / 2, cnt_mn = n / 2;
	vector<pll> ans;
	memset(flag, false, sizeof flag);

	for (int i = 0; i < n; i++) {
		if (mn_vec[i].empty() && cnt_mx) {
			ans.push_back({i, mx_vec[i].back()});
			mx_vec[i].pop_back();
			cnt_mx--;
			flag[i] = true;
		}
	}

	for (int i = 0; i < n; i++) {
		if (!flag[i] && mx_vec[i].empty() && cnt_mn) {
			ans.push_back({i, mn_vec[i].back()});
			mn_vec[i].pop_back();
			cnt_mn--;
			flag[i] = true;
		}
	}

	for (int i = 0; i < n; i++) {
		if (flag[i]) continue;

		bool tmp = false;
	
		if (!cnt_mn) tmp = true;
		if (cnt_mn && cnt_mx && (mx_vec[i].size() > mn_vec[i].size())) tmp = true;
		
		//cerr << tt << ": " << cnt_mn << sep << cnt_mx << sep << tmp << endl;

		if (tmp) ans.push_back({i, mx_vec[i].back()}), mx_vec[i].pop_back(), cnt_mx--;
		else ans.push_back({i, mn_vec[i].back()}), mn_vec[i].pop_back(), cnt_mn--;
	}

	sort(all(ans), [] (const pll& a, const pll& b) {
		return A[a.X][a.Y] < A[b.X][b.Y];
	});

	for (int i = 0; i < n / 2; i++)
		fans -= A[ans[i].X][ans[i].Y];

	for (int i = n / 2; i < n; i++)
		fans += A[ans[i].X][ans[i].Y];

	for (auto [x, y] : ans) {
		res[x][y] = tt;
		
//		cerr << x << "," << y << sep;
	}

//	cerr << endl;
	
//	debug(fans)
	tt++;
}

set<pll> pst, nst; 

inline void add(int i) {
	if (len[i]) pst.insert(pll(A[i][len[i] - 1] + A[i][m - 1 - (k - len[i])], i));
	if (len[i] < k) nst.insert(pll(A[i][len[i]] + A[i][m - (k - len[i])], i));
}

inline void remove(int i) {
	if (len[i]) pst.erase(pll(A[i][len[i] - 1] + A[i][m - 1 - (k - len[i])], i));
	if (len[i] < k) nst.erase(pll(A[i][len[i]] + A[i][m - (k - len[i])], i));
}
 
ll find_maximum(int k_, vector<vector<int>> A_) {
	A = A_;
	k = k_;
	n = A.size();
	m = A[0].size();
 
	res.resize(n);
	for (auto& e : res) {
		e.resize(m);
		for (int& x : e)
			x = -1;
	}

	vector<pll> vec;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			vec.push_back({i, j});

	sort(all(vec), [] (const pll& a, const pll& b) {
		return A[a.X][a.Y] < A[b.X][b.Y];
	});

	if (k == m) {
		int s = n * m;
		for (int i = 0; i < s / 2; i++)
			mn_vec[vec[i].X].push_back(vec[i].Y);
		for (int i = s / 2; i < s; i++)
			mx_vec[vec[i].X].push_back(vec[i].Y);
		
		for (int i = 0; i < k; i++)
			get();

		allocate_tickets(res);
		return fans;
	}

	for (int i = 0; i < n / 2; i++) {
		len[i] = k;
		add(i);
	}

	for (int i = n / 2; i < n; i++) {
		len[i] = 0;
		add(i);
	}

	while (true) {
		vector<pll> nst_f;
		vector<pll> pst_f;

		if (!nst.empty()) nst_f.push_back(*nst.begin());
		if (int(nst.size()) > 1) nst_f.push_back(*next(nst.begin()));

		if (!pst.empty()) pst_f.push_back(*pst.rbegin());
		if (int(pst.size()) > 1) pst_f.push_back(*next(pst.rbegin()));

		pair<int, pll> best = make_pair(-1, make_pair(0, 0));
		for (pll e1 : nst_f) {
			for (pll e2 : pst_f) {
				if (e1.Y == e2.Y) continue;
				ll score = e2.X - e1.X;
				if (score > best.X)
					best = {score, {e2.Y, e1.Y}};
			}
		}

		if (best.X <= 0) break;

		int u = best.Y.X, v = best.Y.Y;
		remove(u), remove(v);

		len[u]--;
		len[v]++;

		add(u);
		add(v);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < len[i]; j++)
			mn_vec[i].push_back(j);

		for (int j = 0; j < k - len[i]; j++)
			mx_vec[i].push_back(m - 1 - j);	
	}

	for (int i = 0; i < k; i++)
		get();

	allocate_tickets(res);
	return fans;
}

• 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