Pagini recente » Cod sursa (job #2699629) | Cod sursa (job #1257296) | Cod sursa (job #290330) | Cod sursa (job #2399327) | Cod sursa (job #2087885)
#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;
}