Submission #1049561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049561		inesfi	Jousting tournament (IOI12_tournament)	C++17	100 / 100	171 ms	9484 KiB

tournament

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

const int TAILLEMAXI=100*1000+2,PUISSMAXI=19,DECALAGE=(1<<18);
int arbremax[2*DECALAGE+1];
int arbresomme[2*DECALAGE+1];
int posdeb[TAILLEMAXI];
vector<pair<int,int>> tours;
vector<pair<int,int>> inter;
int deb,fin,milieu,val,premier,dernier,nbfois,ec,rec,rep;
int cumu[TAILLEMAXI];

int somme(int a,int b){
    if (a==b){
        return arbresomme[a];
    }
    if (a%2==1){
        return arbresomme[a]+somme(a+1,b);
    }
    if (b%2==0){
        return arbresomme[b]+somme(a,b-1);
    }
    return somme(a/2,b/2);
}

int maxi(int a,int b){
    if (a==b){
        return arbremax[a];
    }
    if (a%2==1){
        return max(arbremax[a],maxi(a+1,b));
    }
    if (b%2==0){
        return max(arbremax[b],maxi(a,b-1));
    }
    return maxi(a/2,b/2);
}

void changer(int a){
    while (a!=0){
        arbresomme[a]++;
        a/=2;
    }
}

int GetBestPosition(int nbpers, int nbtours, int nouvpers, int *K, int *S, int *E) {
    for (int i=0;i<nbpers-1;i++){
        posdeb[i]=K[i];
        arbremax[DECALAGE+i]=posdeb[i];
    }
    for (int i=DECALAGE-1;i>=0;i--){
        arbremax[i]=max(arbremax[i*2],arbremax[i*2+1]);
    }
    for (int i=0;i<nbtours;i++){
        tours.push_back(make_pair(S[i],E[i]));
    }
    for (int i=0;i<nbtours;i++){
        deb=0;
        fin=nbpers-1;
        while (deb<fin){
            milieu=(deb+fin+1)/2;
            val=somme(0+DECALAGE,milieu-1+DECALAGE);
            if (milieu-val>=tours[i].first){
                fin=milieu-1;
            }
            else {
                deb=milieu;
            }
        }
        if (arbresomme[deb+DECALAGE]==0 and tours[i].first!=0){
            deb++;
        }
        premier=deb;
        deb=0;
        fin=nbpers;
        //cout<<somme(DECALAGE,4+DECALAGE)<<endl;
        while (deb<fin){
            milieu=(deb+fin)/2;
            val=somme(0+DECALAGE,milieu-1+DECALAGE);
            if (milieu-val>tours[i].second){
                fin=milieu;
            }
            else {
                deb=milieu+1;
            }
        }
        deb--;
        dernier=deb;
        inter.push_back({premier,dernier});
        deb=0;
        nbfois=dernier-premier+1-somme(premier+DECALAGE,dernier+DECALAGE)-1;
        for (int j=0;j<nbfois;j++){
            deb=premier;
            fin=dernier;
            while (deb<fin){
                milieu=(deb+fin)/2;
                val=somme(deb+DECALAGE,milieu+DECALAGE);
                if (val!=milieu-deb+1){
                    fin=milieu;
                }
                else {
                    deb=milieu+1;
                }
            }
            changer(deb+DECALAGE);
        }
    }
    for (int i=0;i<nbtours;i++){
        //cout<<inter[i].first<<" "<<inter[i].second<<endl;
        val=maxi(inter[i].first+DECALAGE,inter[i].second-1+DECALAGE);
        if (val<nouvpers){
            //cout<<42<<endl;
            cumu[inter[i].first]++;
            cumu[inter[i].second+1]--;
        }
    }
    rec=-1;
    for (int i=0;i<nbpers;i++){
        ec+=cumu[i];
        if (ec>rec){
            rec=ec;
            rep=i;
        }
    }
    //cout<<rep<<endl;
    return rep;
}

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