Cod sursa(job #2117825)

Utilizator alexradu04Radu Alexandru alexradu04 Data 29 ianuarie 2018 18:46:28
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>

using namespace std;


const int MAX_N = 30000;

int Place[1 + MAX_N];
int ArbInt[4 * MAX_N+1];
int FinalPlace[1 + MAX_N];

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

void FindFinalPlace(int nod, int st, int dr, int index, int place)
{
    if(st == dr)
    {
        ArbInt[nod] = 0;
        FinalPlace[st] = place;
        return;
    }
    int mid = (st + dr) / 2;
    if(index <= ArbInt[2 * nod])
        FindFinalPlace(2 * nod, st, mid, index, place);
    else
        FindFinalPlace(2 * nod + 1, mid + 1, dr, index - ArbInt[2 * nod], place);
    ArbInt[nod] = ArbInt[2 * nod] + ArbInt[2 * nod + 1];
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d",&Place[i]);
        Build(1, 1, n, i);
    }
    for(int i = n; i > 0; i--)
        FindFinalPlace(1, 1, n, Place[i], i);
    for(int i = 1; i <= n; i++)
        printf("%d\n",FinalPlace[i]);
    return 0;
}