Pagini recente » Winter Challenge, Clasament pentru clasele IX-X | Cod sursa (job #180122) | Cod sursa (job #2236551) | Cod sursa (job #97106) | Cod sursa (job #2087879)
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
struct interval
{
int leftBoundary, rightBoundary;
int value; /// The values of its son and itself :)
interval *leftSon, *rightSon;
};
const int 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;
int 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, int leftBoundary, int rightBoundary)
{
root = new interval;
root->leftBoundary = leftBoundary;
root->rightBoundary = rightBoundary;
createSons(root);
}
int query_index(interval *x, int offset, int 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, int index, int 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;
int place[N]; /// Input Array
int n;
/// Input
in>>n;
for(int i=0; i<n; ++i)
in>>place[i];
/// Create the interval tree
createIntervalTree(rootInterval, 1, n);
/// Initialize the interval tree
for(int i=1; i<=n; ++i)
updateIndex(rootInterval, i, 1);
/// Solve the problem
int sol[N];
for(int i=n-1; i>=0; --i)
{
int index = query_index(rootInterval, 0, place[i]);
sol[index] = i+1;
updateIndex(rootInterval, index, -1); /// Insert the current Element into the tree
}
for(int j=1; j<=n; ++j)
out<<sol[j]<<" ";
return 0;
}