Submission #429909

#	Time	Username	Problem	Language	Result	Execution time	Memory
429909		Mounir	Jousting tournament (IOI12_tournament)	C++14	0 / 100	22 ms	1484 KiB

tournament

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

const int N = (1 << 18);
int nPartis[N * 2];
int cumul[N], res[N];

bool onGagne(int fin, int deb){
	int sum = cumul[fin];
	if (deb > 0)
		sum -= cumul[deb - 1];
	return (sum == 0);
}

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) {
	for (int iRound = 0; iRound < nRounds; ++iRound){
		int compression  = droite[iRound] - gauche[iRound];
		gauche[iRound] = getKth(1, N, gauche[iRound]);
		droite[iRound] += getKth(1, N, droite[iRound]);
		for (int noeud = N + gauche[iRound]; noeud > 0; noeud /= 2)
			nPartis[noeud] += compression;
//		cout << "inter " << gauche[iRound] << " " << droite[iRound] << endl;
	}

	for (int ind = 0; ind < nGars - 1; ++ind){
		cumul[ind] = (rangs[ind] > rangPaume);
		if (ind != 0)
			cumul[ind] += cumul[ind - 1];
	}

	for (int iRound = 0; iRound < nRounds; ++iRound){
		if (onGagne(gauche[iRound], droite[iRound])){
			res[gauche[iRound]]++;
			res[droite[iRound] + 1]--;
		}
	}
	

	int iOpt = 0;
	//cout << "res " << res[0] << " ";
	for (int ind = 1; ind < nGars; ++ind){
		res[ind] += res[ind - 1];
	//	cout << res[ind] << " ";
		if (res[ind] > res[iOpt])
			iOpt = ind;
	}
//	cout << endl;
	return iOpt;
}

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