Cod sursa(job #1350654)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 20 februarie 2015 21:19:51
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#define N 30005
using namespace std;
int a[3*N],s[N],b[N];
int n,poz,val,k;
void Update(int nod,int st,int dr)
{
    if(st==dr)
    {
        a[nod]=val;
        return ;
    }
    int mij=(st+dr)/2;
    if(poz<=mij) Update(2*nod,st,mij);
    else Update(2*nod+1,mij+1,dr);
    a[nod]=a[2*nod]+a[2*nod+1];
}
int Query(int nod,int st,int dr)
{
    if(st==dr) return st;
    int mij=(st+dr)/2;
    if(a[2*nod]>=val) return Query(nod*2,st,mij);
    val-=a[nod*2];
    return Query(2*nod+1,mij+1,dr);
}
int main()
{
    ifstream fin("schi.in");
    ofstream fout("schi.out");
    fin>>n;
    int i,j;
    for(i=1; i<=n; i++)
    {
        fin>>b[i];
        poz=i;
        val=1;
        Update(1,1,n);
    }
    k=1;
    while(n>=(1<<k)) k++;
    k=(1<<k)-n-1;
    //cout<<k<<"\n";
//        for(i=1; i<=2*n; i++)
//        cout<<a[i]<<" ";
//        cout<<"\n";
    for(i=n; i>=1; i--)
    {
        val=b[i];
        poz=Query(1,1,n);
        val=0;
        Update(1,1,n);
        s[poz]=i;
//        cout<<poz<<"\n";
//               for(j=1; j<=2*n; j++)
//        cout<<a[j]<<" ";
//        cout<<"\n";
    }
    for(i=1; i<=n; i++)
        fout<<s[i]<<"\n";

    return 0;
}