제출 #429599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429599		Mounir	마상시합 토너먼트 (IOI12_tournament)	C++14	0 / 100	1076 ms	2264 KiB

tournament

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

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

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

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; ++ind)
			rangsCur.pb(rangs[ind]);

		int iRound;
		for (iRound = 0; iRound < nRounds; ++iRound){
			vector<int> participants;
			for (int ind = gauche[iRound]; ind <= droite[iRound]; ++ind)
				participants.pb(getKth(1, N, ind));

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

			bool fin = false;
			for (int participant : participants){
				if (participant == depart && participant != iBest)
					fin = true;
			}
			if (fin)
				break;

			for (int participant : participants)
				partir(participant);
		}

		if (iRound > tempsOpt){
			tempsOpt = iRound;
			iOpt = depart;
		}
	}
	return iOpt + 1;
}

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