Cod sursa(job #2087885)

Utilizator Andreiii500Andrei Puiu Andreiii500 Data 14 decembrie 2017 14:50:00
Problema Schi Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.2 kb
#include<iostream>
#include<fstream>
using namespace std;

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

struct interval
{
    short leftBoundary, rightBoundary;
    short value; /// The values of its son and itself :)
    interval *leftSon, *rightSon;
};

const short N = 30001;

void createSons(interval *x)
{
    x->value = 0;

    ////cout<<"Father\n";
    //cout<<"("<<x->leftBoundary<<", "<<x->rightBoundary<<")\n";

    if(x->leftBoundary == x->rightBoundary)
    {
        x->leftSon = NULL;
        x->rightSon = NULL;
    }
    else if(x->leftBoundary < x->rightBoundary)
    {
        interval *leftSon = new interval;
        interval *rightSon = new interval;

        short middleBoundary = (x->leftBoundary + x->rightBoundary) / 2;

        leftSon->leftBoundary = x->leftBoundary;
        leftSon->rightBoundary = middleBoundary;

        rightSon->leftBoundary = middleBoundary + 1;
        rightSon->rightBoundary = x->rightBoundary;

        x->leftSon = leftSon;
        x->rightSon = rightSon;

        //cout<<"Left son\n";
        createSons(leftSon);
        //cout<<"Right son\n";
        createSons(rightSon);
        //cout<<"End__\n";
    }
    else
    {
        cerr<<"Error! Left boundary > Right boundary\n";
    }
}

void createIntervalTree(interval *&root, short leftBoundary, short rightBoundary)
{
    root = new interval;
    root->leftBoundary = leftBoundary;
    root->rightBoundary = rightBoundary;
    createSons(root);
}

short query_index(interval *x, short offset, short index) /// Finds the first NOT NULL index in the terminal nodes
{
    if(!x) /// We shouldn't reach a NULL node. Ever.
        return -1;

    if(x->leftBoundary == x->rightBoundary) /// We've found our index!
        return x->leftBoundary; /// leftBoundary ( = rightBoundary) acts as an index

    if(index <= offset + x->leftSon->value)
        return query_index(x->leftSon, offset, index);
    else
        return query_index(x->rightSon, offset + x->leftSon->value, index); /// Skip all left indexes by adding them to the offset
}

void updateIndex(interval *x, short index, short value)
{
    if(!x) /// NULL node reached
        return;

    if(index < x->leftBoundary || index > x->rightBoundary) /// Index is outside interval
    {
        return;
    }
    else
    {
        x->value += value;
        updateIndex(x->leftSon, index, value);
        updateIndex(x->rightSon, index, value);
    }
}

int main()
{
    /// Variables
    interval *rootInterval;
    short place[N]; /// Input Array
    short n;

    /// Input
    in>>n;
    for(short i=0; i<n; ++i)
        in>>place[i];

    /// Create the interval tree
    createIntervalTree(rootInterval, 1, n);

    /// Initialize the interval tree
    for(short i=1; i<=n; ++i)
        updateIndex(rootInterval, i, 1);

    /// Solve the problem
    short sol[N];
    for(short i=n-1; i>=0; --i)
    {
        short index = query_index(rootInterval, 0, place[i]);
        sol[index] = i+1;
        updateIndex(rootInterval, index, -1); /// Insert the current Element into the tree
    }

    for(short j=1; j<=n; ++j)
        out<<sol[j]<<"\n";

    return 0;
}