Submission #823250

#	Time	Username	Problem	Language	Result	Execution time	Memory
823250		Sohsoh84	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	468 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;
vector<vector<int>> res, A;
bool flag[MAXN]; 

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 (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;

		else 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++;
}

ll find_maximum(int k, vector<vector<int>> A_) {
	A = A_;
	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];
	});

	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;
}

• Subtask 1: 0 / 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