Cod sursa(job #1804545)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 12 noiembrie 2016 18:36:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int n,i,poz,x,v[1<<15],sol[1<<15],A[1<<17];
inline void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        A[nod]=1;
        return ;
    }
    int mid=(st+dr)>>1;
    int left=nod<<1;
    build(left,st,mid);
    build(left+1,mid+1,dr);
    A[nod]=A[left]+A[left+1];
}
inline int search(int nod,int st,int dr)
{
    if(st==dr) return st;
    int mid=(st+dr)>>1;
    int left=nod<<1;
    if(x<=A[left]) return search(left,st,mid);
    else
    {
        x-=A[left];
        return search(left+1,mid+1,dr);
    }
}
inline void update(int nod,int st,int dr)
{
    A[nod]--;
    if(st==dr) return ;
    int mid=(st+dr)>>1;
    int left=nod<<1;
    if(poz<=mid) update(left,st,mid);
    else update(left+1,mid+1,dr);
}
int main()
{
    f>>n;
    for(i=1;i<=n;++i) f>>v[i];
    build(1,1,n);
    for(i=n;i;--i)
    {
        x=v[i];
        poz=search(1,1,n);
        sol[poz]=i;
        update(1,1,n);
    }
    for(i=1;i<=n;++i) g<<sol[i]<<'\n';
    return 0;
}