Cod sursa(job #1207127)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 12 iulie 2014 12:52:17
Problema Schi Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
using namespace std;

ifstream is("schi.in");
ofstream os("schi.out");

typedef int Arb;
int N, a[30003], x, y, R[30003];
Arb A[30003];

void Input();
void Solve();
void Build(int, int, int);
void Update(int, int, int);

int main()
{
    Input();
    Solve();

    is.close();
    os.close();
}

void Input()
{
    is >> N;
    for ( int i = 1; i <= N; ++i )
    {
        is >> a[i];
        x = i;
        Build(1,1,N);
    }

}

void Solve()
{
    for ( int i = N; i >= 1; --i )
    {
        x = i;
        y = a[i];
        Update(1,1,N);
    }
    for ( int i = 1; i <= N; ++i )
        os << R[i] << '\n';
}

void Build(int node, int left, int right)
{
    if ( left == right )
    {
        A[node] = 1;
        return;
    }

    int mid = (left+right)/2;

    if ( x <= mid ) Build(2*node,left,mid);
    else    Build(2*node+1,mid+1,right);

    A[node] = A[node*2] + A[node*2+1];
}

void Update(int node, int left, int right)
{
    if ( left == right )
    {
        A[node] = 0;
        R[left] = x;
        return;
    }

    int mid = (left+right)/2;

    if ( y <= A[node*2] )
        Update(node*2,left,mid);
    else
    {
        y -= A[node*2];
        Update(node*2+1,mid+1,right);
    }
    A[node] = A[node*2] + A[node*2+1];
}