Submission #1167385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167385		gyg	Carnival Tickets (IOI20_tickets)	C++20	14 / 100	377 ms	107032 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define sig signed 
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
#define mp make_pair
const int N = 1505, M = 1505, INF = 1e18;

int n, m, k;
arr<arr<int, M>, N> a;

arr<int, N> zr, on;
void intl() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 0) zr[i]++;
			else on[i]++;
		}
	}
}

arr<arr<vec<int>, 2>, N> upd;
int upd_cmp() {
	int ans = 0;
	for (int r = 1; r <= k; r++) {
		vec<pii> ord;
		for (int i = 1; i <= n; i++) ord.push_back({on[i], i});
		sort(ord.begin(), ord.end());

		for (int i = 1; i <= n; i++) {
			pii x = ord[i - 1];
			if (on[x.sec] == 0 || (zr[x.sec] != 0 && i <= n / 2)) {
				zr[x.sec]--;
				upd[x.sec][0].push_back(r);
			} else {
				on[x.sec]--;
				upd[x.sec][1].push_back(r);
				ans += (i <= n / 2) ? -1 : +1;
			}
		}
	}
	return ans;
}

arr<arr<int, M>, N> ass;
void ass_cmp() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == 0 && upd[i][0].size())
				ass[i][j] = upd[i][0].back(), upd[i][0].pop_back();
			if (a[i][j] == 1 && upd[i][1].size())
				ass[i][j] = upd[i][1].back(), upd[i][1].pop_back(); 
		}
	}
}


// Return indices 0-indexed
int find_maximum(sig _k, vec<vec<sig>> _a) {
	n = _a.size(), m = _a[0].size(), k = _k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			a[i][j] = _a[i - 1][j - 1];

	intl();
	int ans = upd_cmp();
	// for (int i = 1; i <= n; i++) {
	// 	for (int j : upd[i][0]) cout << i << " 0 " << j << '\n';
	// 	for (int j : upd[i][1]) cout << i << " 1 " << j << '\n';
	// }
	ass_cmp();
	
	vec<vec<sig>> x;
	for (int i = 1; i <= n; i++) {
		vec<sig> y;
		for (int j = 1; j <= m; j++) y.push_back(ass[i][j] - 1);
		x.push_back(y);
	}
	allocate_tickets(x);
	return ans;
}

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