Cod sursa(job #392199)

Utilizator ionutz32Ilie Ionut ionutz32 Data 6 februarie 2010 22:47:55
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <ctime>
#include <stdlib.h>
struct nod
{
	int val,s,p;
	nod *st,*dr;
};
int n,i,poz,pas;
nod *t,*u,*aux;
int rangs(nod *treap)
{
	if (treap->st==NULL)
		return 0;
	return treap->st->s;
}
int rangd(nod *treap)
{
	if (treap->dr==NULL)
		return 0;
	return treap->dr->s;
}
int ps(nod *treap)
{
	if (treap->st==NULL)
		return 0;
	return treap->st->p;
}
int pd(nod *treap)
{
	if (treap->dr==NULL)
		return 0;
	return treap->dr->p;
}
void rotleft(nod *&treap)
{
	u=treap->st;
	treap->st=u->dr;
	u->dr=treap;
	u->s=rangs(u)+rangs(treap)+rangd(treap)+2;
	treap->s=rangs(treap)+rangd(treap)+1;
	treap=u;
}
void rotright(nod *&treap)
{
	u=treap->dr;
	treap->dr=u->st;
	u->st=treap;
	u->s=rangd(u)+rangs(treap)+rangd(treap)+2;
	treap->s=rangs(treap)+rangd(treap)+1;
	treap=u;
}
void balance(nod *&treap)
{
	if (treap->st!=NULL && treap->st->p>treap->p)
		rotleft(treap);
	else
		if (treap->dr!=NULL && treap->dr->p>treap->p)
			rotright(treap);
}
void insert(nod *&treap,int val,int poz,int p)
{
	if (treap==NULL)
	{
		treap=new nod;
		treap->val=val;
		treap->s=0;
		treap->p=p;
		treap->st=NULL,treap->dr=NULL;
	}
	else
		if (poz<=rangs(treap))
			insert(treap->st,val,poz,p);
		else
			insert(treap->dr,val,poz-rangs(treap)-1,p);
	++treap->s;
	balance(treap);
}
void sterge(nod *&treap)
{
	if (treap->st==NULL && treap->dr==NULL)
		delete treap,treap=NULL;
	else
	{
		if (ps(treap)>pd(treap))
		{
			rotleft(treap);
			sterge(treap->dr);
		}
		else
		{
			rotright(treap);
			sterge(treap->st);
		}
		--treap->s;
	}
}
int access(nod *&treap,int poz)
{
	int ret;
	if (poz<=rangs(treap))
		ret=access(treap->st,poz);
	else
		if (poz>rangs(treap)+1)
			ret=access(treap->dr,poz-rangs(treap)-1);
		else
		{
			ret=treap->val;
			sterge(treap);
			return ret;
		}
	--treap->s;
	return ret;
}
int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	scanf("%d",&n);
	srand(unsigned(time(0)));
	for (i=1;i<=n;++i)
		insert(t,i,i,rand()+1);
	poz=2;
	do
	{
		printf("%d ",access(t,poz));
		++pas;
		--n;
		if (!n)
			break;
		poz=(poz+pas)%n;
		if (!poz)
			poz=n;
	}
	while (n);
	return 0;
}