Pagini recente » Cod sursa (job #1410275) | Cod sursa (job #1914592) | Cod sursa (job #810583) | Cod sursa (job #2527283) | Cod sursa (job #3134118)
#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]);
}
}
void afis(nod *& t)
{
if(t->c[0]) afis(t->c[0]);
cout << t->id << '\n';
if(t->c[1]) afis(t->c[1]);
}
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);
}
afis(treap);
return 0;
}