Submission #604050

#	Time	Username	Problem	Language	Result	Execution time	Memory
604050		HamletPetrosyan	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	834 ms	114508 KiB

tickets

#include "tickets.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long
#define pll pair<long long, long long>
#define add push_back
#define all(a) (a).begin(), (a).end()
#define len(a) ((int)(a).size())

#define fr first
#define sc second

ll n, m;
vector<vector<int>> answer;
vector<int> h, l, r;

ll pl = 0, mi = 0, bo = 0;

void init(int k){
	for(int i = 0; i < n; i++){
		if(h[i] == 0) {
			mi++;
			l[i] = 0;
		}
		else if(h[i] == k) {
			pl++;
			r[i] = m - 1;
		}
		else {
			bo++;
			l[i] = 0;
			r[i] = m - 1;
		}
	}
}

void constructsol(int k){
	ll mins = n / 2 - mi, pls = n / 2 - pl;
	for(int i = 0; i < n; i++){
		if(h[i] == 0){
			answer[i][l[i]] = k;
			l[i]++;
		}
		else if(h[i] == k + 1){
			answer[i][r[i]] = k;
			h[i]--;
			r[i]--;
		}
		else {
			if(mins > 0){
				answer[i][l[i]] = k;
				l[i]++;
				mins--;
				if(h[i] == k) pl++;
			}
			else{
				answer[i][r[i]] = k;
				h[i]--;
				if(h[i] == 0) mi++;
				r[i]--;
				pls--;
			}
		}
	}
}

long long find_maximum(int k, vector<vector<int>> x) {
	n = len(x);
	m = len(x[0]);

	answer.resize(n);
	for(int i = 0; i < n; i++){
		answer[i].resize(m, -1);
	}

	vector<pll> v;
	h.resize(len(x));
	l.resize(len(x));
	r.resize(len(x));

	long long res = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++){
			res -= x[i][j];
			v.add({x[i][m - k + j] + x[i][j], i});
		}
	}

	sort(all(v));

//	cout << res << endl;
//	cout << "----------v---------" << endl;
//	for(int i = 0; i < len(v); i++){
//		cout << v[i].fr << " " << v[i].sc << endl;
//	}
//	cout << endl;

	for(int i = len(v) - 1; i >= len(v) - (n * k / 2); i--){
		h[ v[i].sc ]++;
		res += v[i].fr;
	}

	init(k);

	while(k--){
		constructsol(k);
	}

	allocate_tickets(answer);
	return res;
}

• 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