Cod sursa(job #1943244)

Utilizator Marius7122FMI Ciltea Marian Marius7122 Data 28 martie 2017 14:19:55
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#define N 30005

int n,i,sol;
int arb[4*N],clasament[N],cp[N];

void build(int st,int dr,int nod)   ///arb[nod]=numarul de locuri disponibile in intervalul [st,dr]
{
    if(st==dr)
    {
        arb[nod]=1;
        return;
    }
    int m=(st+dr)/2;
    build(st,m,2*nod);
    build(m+1,dr,2*nod+1);
    arb[nod]=arb[2*nod]+arb[2*nod+1];
}
void query(int st,int dr,int nod,int val)
{
    arb[nod]--;
    if(st==dr)
    {
        sol=st;
        return;
    }
    int m=(st+dr)/2;
    if(arb[2*nod]>=val)
        query(st,m,2*nod,val);
    else
        query(m+1,dr,2*nod+1,val-arb[2*nod]);
}
int main()
{
    FILE *f1,*f2;
    f1=fopen("schi.in","r");
    f2=fopen("schi.out","w");

    fscanf(f1,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(f1,"%d",&cp[i]);

    build(1,n,1);

    for(i=n;i>0;i--)
    {
        query(1,n,1,cp[i]);
        clasament[sol]=i;
    }

    for(i=1;i<=n;i++)
        fprintf(f2,"%d ",clasament[i]);

    return 0;
}