Pagini recente » Cod sursa (job #1596903) | Cod sursa (job #498186) | Cod sursa (job #1914062) | Cod sursa (job #2357561) | Cod sursa (job #3134149)
#include<fstream>
#include<random>
#include<ctime>
using namespace std;
ifstream cin("schi.in");
ofstream cout("schi.out");
mt19937 rng(time(nullptr));
struct nod
{
int id,p,sz; nod *c[2];
nod(int &g) : id(g),p(rng()),sz(1) {c[0] = NULL,c[1] = NULL;}
};
int size(nod *& treap){return treap ? treap->sz : 0;}
void split(nod *r,nod *&st,nod *&dr,int &x,int cheie)
{
if(!r) st = NULL,dr = NULL;
else
{
cheie += size(r->c[0]);
if(cheie <= x) split(r->c[1],r->c[1],dr,x,cheie + 1),st = r;
else split(r->c[0],st,r->c[0],x,cheie - size(r->c[0])),dr = r;
r->sz = 1 + size(r->c[0]) + size(r->c[1]);
}
}
void merge(nod *&r,nod *st,nod *dr)
{
if(!st || !dr) r = st ? st : dr;
else
{
if(st->p < dr->p) merge(st->c[1],st->c[1],dr),r = st;
else merge(dr->c[0],st,dr->c[0]),r = dr;
r->sz = 1 + size(r->c[0]) + size(r->c[1]);
}
}
ostream &operator<<(ostream &out,nod *&a)
{
if(a->c[0]) out << a->c[0];
out << a->id << '\n';
if(a->c[1]) out << a->c[1];
return out;
}
int main()
{
int n,a; cin >> n; nod *treap = nullptr;
for(int i = 1; i <= n ; i++)
{
cin >> a; a -= 2; nod *st = NULL,*dr = NULL;
split(treap,st,dr,a,0);
merge(st,st,new nod(i)); merge(treap,st,dr);
}
cout << treap;
return 0;
}