Pagini recente » Cod sursa (job #2134136) | Cod sursa (job #1590853) | Cod sursa (job #1004493) | Cod sursa (job #2231666) | Cod sursa (job #1399098)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream F("schi.in");
ofstream G("schi.out");
struct item {
int sz,vl,pr;
item *l , *r;
item() {
}
item(int vl)
{
this->vl = vl;
l = r = NULL;
pr = (rand() << 16) ^ rand();
sz = 1;
}
};
#define tree item*
void compute(tree &t)
{
if ( t == NULL ) return;
t->sz = 1;
t->sz += t->l ? t->l->sz : 0;
t->sz += t->r ? t->r->sz : 0;
}
void split(tree t,int pl,tree &l,tree &r)
{
if ( t == NULL )
{
l = r = NULL;
return;
}
int sl = t->l ? t->l->sz : 0;
if ( pl <= sl )
{
split(t->l,pl,l,t->l); // tai la pl
r = t;
}
else
{
split(t->r,pl-sl-1,t->r,r); // tai la pl-sl-1
l = t;
}
compute(l);
compute(r);
}
void insert(tree &t,int pl,tree x)
{
int sl = t ? t->l ? t->l->sz : 0 : 0;
if ( !t )
t = x;
else
if ( t->pr > x->pr )
{
split(t,pl,x->l,x->r);
t = x;
}
else
{
if ( pl <= sl )
insert(t->l,pl,x);
else
insert(t->r,pl-sl-1,x);
}
compute(t);
}
void print(tree t)
{
if ( t->l )
print(t->l);
G<<t->vl<<'\n';
if ( t->r )
print(t->r);
}
void printd(tree t)
{
if ( t->l )
printd(t->l);
cerr<<t->vl<<' ';
if ( t->r )
printd(t->r);
}
int n;
tree t = NULL;
int main()
{
srand(time(0));
F>>n;
for (int i=1,p;i<=n;++i)
{
F>>p;
tree x = new item(i);
insert(t,p-1,x);
// printd(t); cerr<<'\n';
}
print(t);
}