Cod sursa(job #3253716)

Utilizator Laura139Anghel Laura Laura139 Data 4 noiembrie 2024 16:29:26
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <cmath>

using namespace std;

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

int arb[65540];

int n,m;
int v[30005];
int rez[30005];

void initializare(int nod,int st, int dr)
{
    if(st==dr)
    {
        if(st<=n)
            arb[nod]=1;
        return;
    }
    int med=(st+dr)/2;
    initializare(2*nod, st, med);
    initializare(2*nod+1, med+1, dr);
    arb[nod]=arb[2*nod]+arb[2*nod+1];
}

int x;

void query(int nod, int loc_l)
{
    //cout<<"Ma aflu in nodul "<< nod<<", avand costul "<<arb[nod]<<", cu locul "<<loc_l<<'\n';
    if(nod>=m && nod<2*m)
    {
        if(arb[nod]==1)
        {
            arb[nod]=0;
            x=nod-m+1;
            //cout<<"Am parcat in locul "<<nod-m+1<<'\n';
        }
        return;
    }
    if(arb[2*nod]<loc_l)
    {
        //cout<<"Am intrat in nodul "<<2*nod+1<<" cu locul "<<loc_l<<'\n';
        query(2*nod+1, loc_l-arb[2*nod]);
    }
    if(arb[2*nod]>=loc_l)
    {
        //cout<<"Am intrat in nodul "<<2*nod<<" cu locul "<<loc_l<<'\n';
        query(2*nod, loc_l);
    }
    arb[nod]=arb[2*nod]+arb[2*nod+1];
}

int main()
{
    cin>>n;
    m=pow(2, floor(log2(n)+!(log2(n)==floor(log2(n)))));
    initializare(1,1,m);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int i=n;i>=1;i--)
    {
        query(1, v[i]);
        rez[x]=i;
        //cout<<'\n';
    }
    for(int i=1;i<=n;i++)
        cout<<rez[i]<<'\n';
    return 0;
}