Cod sursa(job #2117832)

Utilizator alexradu04Radu Alexandru alexradu04 Data 29 ianuarie 2018 18:50:13
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>

using namespace std;

ifstream cin ("schi.in");
ofstream cout ("schi.out");

const int MAX_N = 30000;
const int SIZE = 102400;
char Buffer[SIZE];
int Place[1 + MAX_N];
int ArbInt[4 * MAX_N];
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()
{
    cin.rdbuf()->pubsetbuf(Buffer, SIZE);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> 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++)
        cout << FinalPlace[i] << "\n";
    return 0;
}