Cod sursa(job #1677560)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 6 aprilie 2016 17:36:53
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

ofstream g("schi.out");

int const NMax = 30005;
int n, pos;
int V[NMax], AINT[4*NMax], Sol[NMax];
char Buffer[10000];
int const Buffer_Size = 10000;

void read(int & nr)
{
    nr = 0;
    while((Buffer[pos] < '0' || Buffer[pos] > '9') && Buffer[pos]!='-'){
        pos++;
        if(pos == Buffer_Size){
            fread(Buffer, 1, Buffer_Size, stdin);
            pos = 0;
        }
    }

    while(Buffer[pos] >= '0' && Buffer[pos] <= '9'){
        nr = nr*10 + Buffer[pos++] - '0';
        if(pos == Buffer_Size){
            fread(Buffer, 1, Buffer_Size, stdin);
            pos = 0;
        }
    }
}

void Read()
{
    freopen("schi.in", "r", stdin);
    fread(Buffer, 1, Buffer_Size, stdin);

    read(n);
    for(int i=1; i<=n; i++)
        read(V[i]);
}

void Build(int nod, int st, int dr)
{
    if(st == dr){
        AINT[nod] = 1;
        return;
    }
    int mid = (st + dr)/2;
    Build(2*nod, st, mid);
    Build(2*nod+1, mid+1, dr);

    AINT[nod] = AINT[2*nod] + AINT[2*nod + 1];
}

void Update(int nod, int st, int dr, int pos)
{
    if(st == dr){
        AINT[nod] = 0;
        return;
    }

    int mid = (st + dr)/2;
    if(pos <= mid)
        Update(2*nod, st, mid, pos);
    if(pos > mid)
        Update(2*nod+1, mid+1, dr, pos);

    AINT[nod] = AINT[2*nod] + AINT[2*nod+1];
}

int Query(int nod, int st, int dr, int loc)
{
    if(st == dr){
        return st;
    }

    int mid = (st + dr)/2;
    if(AINT[2*nod] >= loc)
        return Query(2*nod, st, mid, loc);
    else{
        loc -= AINT[2*nod];
        return Query(2*nod+1, mid+1, dr, loc);
    }
}

void Solve()
{
    int i, aux;

    Build(1, 1, n);
    for(i=n; i>0; i--){
        aux = Query(1, 1, n, V[i]);
        Sol[aux] = i;
        Update(1, 1, n, aux);
    }

    for(i=1; i<=n; i++)
        g<<Sol[i]<<"\n";
}

int main()
{
    Read();
    Solve();
    return 0;
}