Cod sursa(job #1229072)

Utilizator lucian666Vasilut Lucian lucian666 Data 16 septembrie 2014 12:13:11
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb



#include <fstream>


#define NMAX 30001
#define lf (nod<<1)
#define rt (lf+1)
#define mid ((st+dr)>>1)

using namespace std;
ofstream out("schi.out");



int n ;

int V[NMAX] , sol[NMAX];

int arb[ NMAX * ( 1 << 2 ) ];

void Read();
void update( int nod , int st , int dr , int poz );
int cauta_poz( int nod ,int st , int dr, int val );
void Solve();
void Write();


int main()
{

    Read();
    Solve();
    Write();

    return 0;

}

void Read()
{

    ifstream in("schi.in");

    in >> n;

    for( int i=1 ; i<=n ; i++)
        in >> V[i];


}

void update( int nod , int st , int dr , int poz )
{

    if( st == dr )
    {

        arb[nod] = 1;
        return;

    }

    if( poz <= mid )
        update( lf , st , mid , poz );
    else
        update( rt , mid + 1 , dr , poz );

    arb[nod] = arb[lf] + arb[rt];


}

int cauta_poz( int nod , int st , int dr , int val )
{

    if( st == dr )
    {

        return st;

    }

    int nr = mid - st + 1 - arb[lf];

    if( nr >= val )
        return cauta_poz(lf , st , mid , val );
    else
    {

        val = val - nr;
        return cauta_poz( rt , mid + 1 , dr , val );

    }

}

void Solve()
{

    for( int i = n ; i >=1 ; --i )
    {

        int val = V[i];
        int poz = cauta_poz( 1 , 1 , n , val );
        update( 1 , 1 , n , poz );
        sol[ poz ] = i;

    }

}

void Write()
{

    for( int i=1 ; i<=n ; i++)
        out << sol[i] << '\n';

}