Cod sursa(job #2560711)

Utilizator MihneaGhiraMihnea MihneaGhira Data 28 februarie 2020 11:03:50
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int n,i;
int v[30010],loc[30010],a[30010];

void build(int st, int dr, int nod){ /// nr de 1 din interval(1 reprezentand ca nu a fost asezat)
    if(st==dr)
        a[nod]=1;
    else{
        int mid=(st+dr)/2;
        build(st,mid,2*nod);
        build(mid+1,dr,2*nod+1);
        a[nod]=a[2*nod]+a[2*nod+1];
    }
}

void clasament(int st, int dr, int nod,int poz){
    if(st==dr){
        a[nod]=0;
        loc[st]=i;
    }
    else{
        int mid;
        mid=(st+dr)/2;
        if(a[2*nod]>=poz){
            clasament(st,mid,2*nod,poz);
        }
        else{
            clasament(mid+1,dr,2*nod+1,poz);
        }
        a[nod]=a[2*nod]+a[2*nod+1];
    }
}

int main(){
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    build(1,n,1);
    for(i=n;i>=1;i--)
        clasament(1,n,1,v[i]);
    for(int i=1;i<=n;i++)
        fout<<loc[i]<<"\n";
    return 0;
}