Cod sursa(job #3155859)

Utilizator mihaiBoantaMihai Boanta mihaiBoanta Data 9 octombrie 2023 23:04:36
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream in("schi.in");
ofstream out("schi.out");

#define nmax 30001
#define inf 100000

int n,narb;
int arbint[nmax*4];

int msb(int n){
    int MSB=1;
    while(n){
        n>>=1;
        MSB<<=1;
    }
    return MSB;
}


struct interval{
    int st,dr;

    bool includes(interval i){
        if(st<=i.st && i.dr<=dr){
            return true;
        }
        return false;
    }

    bool intersects(interval i){
        if(st>i.dr || i.st>dr){
            return false;
        }
        return true;
    }
}arb[nmax*4];

void build(){
    narb=msb(n);
    for(int i=narb;i<2*narb;i++){
        arbint[i]=1;
        arb[i].st=arb[i].dr=i-narb+1;
    }
    for(int i=narb-1;i>0;i--){
        arbint[i]=arbint[2*i]+arbint[2*i+1];
        arb[i].st=arb[2*i].st;
        arb[i].dr=arb[2*i+1].dr;
    }
}
void update(int loc){
    int nod=narb+loc-1;
    arbint[nod]=0;
    while(nod){
        nod/=2;
        arbint[nod]--;
    }
} 
int query(int nod,int val){
    if(nod>=narb){
        return nod-narb+1;
    }

    int found;
    if(arbint[2*nod]<val){
        found=query(2*nod+1,val-arbint[2*nod]);
    }else{
        found=query(2*nod,val);
    }
    return found;
}
int main()
{
    int clasament[nmax];
    in>>n;
    for(int i=1;i<=n;i++){
        in>>clasament[i];
    }
    build();
    int final[nmax];
    for(int i=n;i>0;i--){
        int poz=query(1,clasament[i]);
        final[poz]=i;
        update(poz);
    }
    for(int i=1;i<=n;i++){
        out<<final[i]<<'\n';
    }
}