#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = (1 << 13);
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 - 1; ++ind)
rangsCur.pb(rangs[ind]);
/*
cout << "depart " << depart << endl;
for (int rang : rangsCur)
cout << rang << " ";
cout << endl;
*/
int nWins = 0;
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));
/*
cout << "participant ";
for (int participant : participants)
cout << rangsCur[participant] << " ";
cout << endl;*/
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);
}
}
if (nWins > tempsOpt){
tempsOpt = nWins;
iOpt = depart;
}
}
return iOpt;
}
