Submission #811110

#	Time	Username	Problem	Language	Result	Execution time	Memory
811110		oscar1f	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	1318 ms	348284 KiB

tickets

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

using namespace std;
using ll=long long;
using vv=vector<vector<ll>>;

const int MAX_SORTE=1505;
ll nbSorte,nbDeChaque,nbTour,autre;
vv val,pris;
vector<ll> listeGrand[MAX_SORTE],listePetit[MAX_SORTE];
vector<tuple<ll,ll,ll>> possi;
set<ll> restants[MAX_SORTE];

ll calcRep() {
	ll sommeRep=0;
	vector<tuple<ll,ll,ll>> listePris;
	vector<vector<int>> rep;
	vector<ll> nbPris,meilleur;
	for (ll i=0;i<nbSorte;i++) {
		rep.push_back({});
		for (ll j=0;j<nbDeChaque;j++) {
			if (pris[i][j]==1) {
				listePris.push_back(make_tuple(val[i][j],i,j));
				rep[i].push_back(0);
			}
			else {
				rep[i].push_back(-1);
			}
		}
		for (ll j=0;j<nbTour;j++) {
			restants[i].insert(j);
		}
	}
	sort(listePris.begin(),listePris.end());
	for (ll i=0;i<(ll)listePris.size();i++) {
		if (i<(ll)listePris.size()/2) {
			sommeRep-=get<0>(listePris[i]);
			listePetit[get<1>(listePris[i])].push_back(get<2>(listePris[i]));
		}
		else {
			sommeRep+=get<0>(listePris[i]);
			listeGrand[get<1>(listePris[i])].push_back(get<2>(listePris[i]));
		}
	} 
	for (ll i=0;i<nbTour;i++) {
		meilleur.push_back(i);
		nbPris.push_back(0);
	}
	for (ll i=0;i<nbSorte;i++) {
		/*cout<<i<<" : ";
		for (auto l:listePetit[i]) {
			cout<<l<<" ";
		}
		cout<<"\t";
		for (auto l:listeGrand[i]) {
			cout<<l<<" ";
		}
		cout<<endl;*/
		sort(meilleur.begin(),meilleur.end(),[&] (int a,int b){
			return nbPris[a]<nbPris[b];
		});
		/*for (int i:meilleur) {
			cout<<i<<" ";
		}
		cout<<endl;*/
		for (ll j=0;j<(ll)listePetit[i].size();j++) {
			rep[i][listePetit[i][j]]=meilleur[j];
			nbPris[meilleur[j]]++;
			restants[i].erase(meilleur[j]);
		}
		for (ll j:listeGrand[i]) {
			auto it=restants[i].begin();
			rep[i][j]=(*it);
			restants[i].erase(it);
		}
	}
	allocate_tickets(rep);
	return sommeRep;
}

ll find_maximum(int k,vector<vector<int>> x) {
	for (auto i:x) {
		val.push_back({});
		for (auto j:i) {
			val.back().push_back((ll)j);
		}
	}
	nbTour=k;
	nbSorte=val.size();
	nbDeChaque=val[0].size();
	for (ll i=0;i<nbSorte;i++) {
		pris.push_back({});
		for (ll j=0;j<nbDeChaque;j++) {
			pris.back().push_back(0);
		}
	}
	for (ll i=0;i<nbSorte;i++) {
		for (ll j=0;j<nbTour;j++) {
			pris[i][j]=1;
			autre=nbDeChaque-nbTour+j;
			possi.push_back(make_tuple(val[i][autre]+val[i][j],i,j));
		}
	}
	sort(possi.begin(),possi.end());
	for (int i=0;i<nbSorte*nbTour/2;i++) {
		pris[get<1>(possi.back())][get<2>(possi.back())]=0;
		pris[get<1>(possi.back())][nbDeChaque-nbTour+get<2>(possi.back())]=1;
		possi.pop_back();
	}
	return calcRep();
}

• 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