#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;
}
