Pagini recente » Cod sursa (job #493912) | Cod sursa (job #1858887) | Cod sursa (job #632805) | Cod sursa (job #2221220) | Cod sursa (job #1438259)
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
/// To be submited
ifstream F("schi.in");
ofstream G("schi.out");
struct item {
int pr,vl,sz;
item *l,*r;
item(int vl)
{
this->vl = vl;
pr = ( rand() << 6 ) ^ rand();
sz = 1;
l = r = NULL;
}
};
#define cart item*
void upd(cart &t)
{
return !t ? void() : void( t->sz = ( t->l ? t->l->sz : 0 ) + ( t->r ? t->r->sz : 0 ) + 1 );
}
void split(cart t,int pl,cart &l,cart &r)
{
if ( !t )
return void(l = r = NULL);
int sz = t->l ? t->l->sz : 0;
if ( pl <= sz )
split(t->l,pl,l,t->l) , r = t;
else
split(t->r,pl-sz-1,t->r,r) , l = t;
upd(l);
upd(r);
}
void insert(cart &t,int pl,cart x)
{
if ( !t )
return void(t = x);
int sz = t->l ? t->l->sz : 0;
if ( t->pr < x->pr )
split(t,pl,x->l,x->r) , t = x;
else
if ( pl <= sz )
insert(t->l,pl,x);
else
insert(t->r,pl-sz-1,x);
upd(t);
}
void print(cart x)
{
if ( x->l ) print(x->l);
G<<x->vl<<'\n';
if ( x->r ) print(x->r);
}
void inline_print(cart x)
{
if ( x->l ) inline_print(x->l);
cerr<<x->vl<<' ';
if ( x->r ) inline_print(x->r);
}
int n;
int main()
{
srand(time(NULL));
F>>n;
cart t = NULL;
for (int i=1,p;i<=n;++i)
{
F>>p;
cart x = new item(i);
insert(t,p-1,x);
//inline_print(t); cerr<<'\n';
}
print(t);
}