Submission #1049591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049591		oscar1f	Jousting tournament (IOI12_tournament)	C++17	100 / 100	35 ms	3944 KiB

tournament

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

const int DECA=(1<<17),MAX_CHEV=100*1000+5;
int nbChev,nbRound,nivNouv;
int nbGau[DECA],nbDro[DECA];
int tropFort[MAX_CHEV],debut[MAX_CHEV],nbGagn[MAX_CHEV],enCours[MAX_CHEV];
vector<int> bataille;

void modif(int pos,int coeff) {
    enCours[pos]=coeff;
    pos+=DECA;
    while (pos>1) {
        if (pos%2==0) {
            nbGau[pos/2]+=coeff;
        }
        else {
            nbDro[pos/2]+=coeff;
        }
        pos/=2;
    }
}

void trouveInter(int pos,int nbAvant,int debInter,int finInter) {
    if (pos<DECA) {
        if (nbAvant>finInter or nbAvant+nbGau[pos]+nbDro[pos]<debInter or nbGau[pos]+nbDro[pos]==0) {
            return;
        }
        trouveInter(2*pos,nbAvant,debInter,finInter);
        trouveInter(2*pos+1,nbAvant+nbGau[pos],debInter,finInter);
    }
    else {
        if (nbAvant+1>=debInter and nbAvant+1<=finInter and enCours[pos-DECA]==1) {
            bataille.push_back(pos-DECA);
        }
    }
}

bool verif(int deb,int fin) {
    return ((tropFort[fin]-tropFort[deb])==0);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    nbChev=N;
    nbRound=C;
    nivNouv=R;
    for (int i=0;i<nbChev-1;i++) {
        tropFort[i+1]=tropFort[i];
        if (K[i]>nivNouv) {
            tropFort[i+1]++;
        }
    }
    for (int i=0;i<nbChev;i++) {
        modif(i,1);
        debut[i]=i;
    }
    int debInter,finInter;
    for (int i=0;i<nbRound;i++) {
        bataille.clear();
        trouveInter(1,0,S[i]+1,E[i]+1);
        /*for (int j:bataille) {
            cout<<j<<" ";
        }*/
        debInter=debut[bataille[0]];
        finInter=bataille.back();
        for (int j=0;j<(int)bataille.size()-1;j++) {
            modif(bataille[j],-1);
        }
        debut[bataille.back()]=debInter;
        if (verif(debInter,finInter)) {
            nbGagn[debInter]++;
            nbGagn[finInter]--;
        }
        //cout<<debInter<<" "<<finInter<<" "<<verif(debInter,finInter)<<endl;
    }
    for (int i=1;i<nbChev;i++) {
        nbGagn[i]+=nbGagn[i-1];
    }
    int rep=0,posRep=0;
    for (int i=0;i<nbChev;i++) {
        if (nbGagn[i]>rep) {
            rep=nbGagn[i];
            posRep=i;
        }
    }
    return posRep;
}

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