Submission #613967

#	Time	Username	Problem	Language	Result	Execution time	Memory
613967		Mounir	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	3015 ms	51724 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmax(x, v) x = max(x, v)
#define chmin(x, v) x = min(x, v)
#define pb push_back
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define x first
#define y second
#define int long long
using namespace std;
 
struct Move
{
	int id;
	int perte;
 
	bool operator<(const Move &autre) const
	{
		if (perte != autre.perte)
			return perte < autre.perte;
		return id < autre.id;
	}
};
 
const long long OO = 1e14;
 
long long find_maximum(signed k, vector<vector<signed>> x)
{
	int nCouleurs = sz(x);
	int TOTAL = 0;
	vector<vector<signed>> ans;
	ans.resize(nCouleurs);
	for (auto& ligne : ans){
		ligne.resize(sz(x[0]));
		for (auto& val : ligne)
			val = -1;
	}

	vector<int> left(nCouleurs, 0), right(nCouleurs, sz(x[0]) - 1);
	// On suppose k = 1
	for (int i = 0; i < k; ++i){
		vector<pii> options(nCouleurs);
		vector<int> vals;
		for (int i = 0; i < nCouleurs; ++i)
		{
			options[i] = {x[i][left[i]], x[i][right[i]]};
			vals.pb(x[i][0]);
			vals.pb(x[i][sz(x[0]) - 1]);
		}
 
		vector<int> utilises;
		int gain = 0;
		sort(all(vals));
		for (int med : vals) {
			vector<Move> moves;
			int tot = 0, enDessous = 0;
			vector<int> left(nCouleurs, 0);
			for (int id = 0; id < nCouleurs; ++id) {
				int perte = 0;
				tot += abs(med - options[id].x);
				enDessous += (options[id].y < med);
				if (options[id].y < med)
					left[id] = 1;
				if (options[id].y < med || options[id].x > med)
					perte = OO;
				else {
					perte = abs(options[id].x - med) - abs(options[id].y - med);
					enDessous++;
					left[id] = 1;
				}
				moves.pb({id, perte});
			}
 
		//cout << tot << endl;
			sort(all(moves));
			int i;
			for (i = 0; enDessous > nCouleurs/2; ++i, --enDessous){
				tot -= moves[i].perte;
				left[moves[i].id] = 0;
			}
 
//if (enDessous >= nCouleurs/2)
//			continue;
/*
		cout << "med" << med << " " << tot << " " << enDessous << endl;
		for (int i : left)
			cout << i << " ";
		cout << endl;*/
			if (tot > gain && enDessous == nCouleurs/2){
				gain = tot;
				utilises = left;
			}
		}
		TOTAL += gain;
		for (int ilig = 0; ilig < nCouleurs; ++ilig){
			if (utilises[ilig])
				ans[ilig][left[ilig]++] = i;
			else
				ans[ilig][right[ilig]--] = i;
		}
	}

/*	for (int utilise : utilises)
		cout << utilise << " ";
	cout << endl;
*/
 
	allocate_tickets(ans);
	return TOTAL;
}

• 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