Submission #429610

#	Time	Username	Problem	Language	Result	Execution time	Memory
429610		Mounir	Jousting tournament (IOI12_tournament)	C++14	17 / 100	1087 ms	2068 KiB

tournament

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int N = (1 << 13);
int nPartis[N * 2];

void partir(int ind, int delta){
	for (int noeud = N + ind; noeud > 0; noeud /= 2)
		nPartis[noeud] += delta;
}

int getKth(int noeud, int tailleInter, int k){ //Le 1 est le premier
	if (noeud >= N)
		return noeud - N;
	int nGauche = tailleInter/2 - nPartis[noeud * 2];
	if (k > nGauche)
		return getKth(noeud * 2 + 1, tailleInter/2, k - nGauche);
	return getKth(noeud * 2, tailleInter/2, k);
}

int GetBestPosition(int nGars, int nRounds, int rangPaume, int *rangs, int *gauche, int *droite) {
	int tempsOpt = -1, iOpt = -1;
	for (int depart = 0; depart < nGars; ++depart){
		for (int ind = 0; ind < 2 * N; ++ind)
			nPartis[ind] = 0;

		vector<int> rangsCur;
		for (int ind = 0; ind < depart; ++ind)
			rangsCur.pb(rangs[ind]);
		rangsCur.pb(rangPaume);
		for (int ind = depart; ind < nGars - 1; ++ind)
			rangsCur.pb(rangs[ind]);

/*
		cout << "depart " << depart << endl;
		for (int rang : rangsCur)
			cout << rang << " ";
		cout << endl;
*/
		int nWins = 0, gagnant = -1;
		for (int iRound = 0; iRound < nRounds; ++iRound){
			vector<int> participants;
			for (int ind = gauche[iRound] + 1; ind <= droite[iRound] + 1; ++ind)
				participants.pb(getKth(1, N, ind));

			int iBest = -1;
			for (int participant : participants){
				if (iBest == -1 || (rangsCur[participant] > rangsCur[iBest]))
					iBest = participant;
			}

			if (iBest == depart)
				nWins++;

			for (int participant : participants){
				if (participant != iBest)
					partir(participant, 1);
			}
			gagnant = iBest;
		}

		if (nWins > tempsOpt){
			tempsOpt = nWins;
			iOpt = depart;
		}

		for (int ind = 0; ind < nGars; ++ind)
			if (ind != gagnant)
				partir(ind, -1);
	}
	return iOpt;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51