Cod sursa(job #3246037)

Utilizator PetruApostolApostol Mihnea Petru PetruApostol Data 1 octombrie 2024 16:40:50
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
using namespace std;

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

#define MAXE 1000001

int aint[4*MAXE];
int rasp[MAXE];
int v[MAXE];

void update(int nod,int st,int dr,int poz,int a){
    if(st==dr){
        aint[nod]+=a;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) update(2*nod,st,mij,poz,a);
    else update(2*nod+1,mij+1,dr,poz,a);
    aint[nod]=aint[nod*2]+aint[nod*2+1];
}
int query(int nod,int st,int dr,int sum,int want){
    if(st==dr) return st;
    int mij=(st+dr)/2;
    if(sum+aint[nod*2]>=want)
        return query(nod*2,st,mij,sum,want);
    else
        return query(nod*2+1,mij+1,dr,sum+aint[nod*2],want);

    return -1;
}
int main()
{
    int n,i,cer,poz,a,aux;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>v[i];
        update(1,1,n,i,1);
    }
    for(i=n;i;i--){
        aux=query(1,1,n,0,v[i]);
        rasp[aux]=i;
        update(1,1,n,aux,-1);
    }
    for(i=1;i<=n;i++) cout<<rasp[i]<<" ";
    return 0;
}