Cod sursa(job #1600098)

Utilizator radarobertRada Robert Gabriel radarobert Data 14 februarie 2016 17:57:26
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>

using namespace std;

unsigned short standings[30002];
unsigned short input[30002];
unsigned short free_l[120002], free_r[120002];
int position, real_pos;

void buildTree(int i, int l, int r)
{
    if (l == r)
    {
        free_l[i] = 1;
        return;
    }
    int mid = (l+r)/2;
    buildTree(2*i, l, mid);
    buildTree(2*i+1, mid+1, r);
    free_l[i] = free_l[2*i] + free_r[2*i];
    free_r[i] = free_l[2*i+1] + free_r[2*i+1];
}

void deletePosition(int i)
{
    if (i == 1)
        return;
    if (i % 2 == 0)
        free_l[i/2]--;
    else
        free_r[i/2]--;
    deletePosition(i/2);
}

void findPosition(int i, int l, int r)
{
    if (l == r)
    {
        real_pos = l;
        deletePosition(i);
        return;
    }
    if (position > free_l[i])
    {
        position -= free_l[i];
        findPosition(2*i+1, (l+r)/2+1, r);
    }
    else
        findPosition(2*i, l, (l+r)/2);
}

int main()
{
    ifstream in("schi.in");
    ofstream out("schi.out");

    int n;
    in >> n;

    buildTree(1, 1, n);

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

    for (int i = n; i > 0; i--)
    {
        position = input[i];
        findPosition(1, 1, n);
        standings[real_pos] = i;
    }

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

    return 0;
}