Cod sursa(job #2770178)

Utilizator RamanujanNeacsu Mihnea Ramanujan Data 19 august 2021 18:20:27
Problema Schi Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#define MAXN 30000
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int a[4*MAXN], order[MAXN], ranks[MAXN], start;
void update(int nod){
    while(nod!=1){
        nod/=2;
        a[nod]=a[2*nod]+a[2*nod+1];
    }
}
void eraseContestant(int node){//stergem un jucator aflat pe pozitie data
    while(node!=1){//cat am unde urca
        a[node]--;//scad
        node/=2;//si urc
    }
}
int findXthGap(int x, int pass){//gasim al x-lea loc gol
    //pass e parametru, o sa-l tot modific, pas=1 la primul apel
    if(pass>=start){
        return pass;//daca sunt jos, intorc
    }
    if(a[2*pass]>=x){
        return findXthGap(x, 2*pass);//daca e necesar sa merg in stanga
    }
    else{
        return findXthGap(x-a[2*pass], 2*pass+1);//daca tre' s-o iau la dreapta
    }
}
int main()
{
    int n; fin>>n;
    start=1;
    while(start<n)
       start<<=1;//calculam de unde pleaca arborele de intervale
    for(int i=start; i<start+n; i++){
        a[i]=1;
        update(i);//facem arborele
    }
    //citim si pozitiile
    for(int i=0; i<n; i++){
        fin>>order[i];
    }
    int pass=1;//va fi pe veci 1, ca nu dau adrese, ci valori
    for(int i=n-1; i>=0; i--){
        int pos=findXthGap(order[i], pass)-start+1;//gasim unde se afla al x-lea concurent
        eraseContestant(findXthGap(order[i], pass));//il scoatem
        ranks[pos]=i+1;//si il adaugam
    }
    for(int i=1; i<=n; i++){
        fout<<ranks[i]<<"\n";
    }
    return 0;
}//si-o intrebare de final: cum sa fac sa vaf mai repede erorile de neatentie?