Cod sursa(job #2068450)

Utilizator vancea.catalincatalin vancea.catalin Data 17 noiembrie 2017 21:52:55
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<iostream>
#include<fstream>
#define DX 30009
using namespace std;
fstream fin("schi.in",ios::in),fout("schi.out",ios::out);
int x[DX],ai[4*DX],poz,r[DX];
void update(int nod,int st,int dr,int poz,int val)
{
    int m=(st+dr)/2,plod=nod*2;
    if(st==dr)
    {
        ai[nod]=val;
        return ;
    }
    if(poz<=m)
        update(plod,st,m,poz,val);
    else
        update(plod+1,m+1,dr,poz,val);

    ai[nod]=ai[plod]+ai[plod+1];
}
void query(int nod,int st,int dr,int val)
{
    int m=(st+dr)/2,plod=nod*2;
    if(st==dr)
    {
        poz=st;
        return ;
    }
    if(val<=ai[plod])
        query(plod,st,m,val);
    else
        query(plod+1,m+1,dr,val-ai[plod]);
}
int main()
{
    int n,i,j;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>x[i];
        update(1,1,n,i,1);
    }
    for(i=n;i>0;i--)
    {
        query(1,1,n,x[i]);
        r[poz]=i;
        //poz este pozitia locului x[i] care este liber
        update(1,1,n,poz,0);
    }
    for(i=1;i<=n;i++)
        fout<<r[i]<<"\n";
}