Cod sursa(job #1024939)

Utilizator geniucosOncescu Costin geniucos Data 9 noiembrie 2013 12:39:44
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
int ras,k,cate,i,n;
struct T
{
    int K,P,nr;
    T *l,*r;
    T(int k,int p,int nr,T *l,T *r)
    {
        this->K=k;
        this->P=p;
        this->nr=nr;
        this->l=l;
        this->r=r;
    }
}*R,*nil;
int Rand(){return ((rand()%32768)<<15)+rand()%32768;}
void rotleft(T *&n)
{
    T *t=n->l;
    int v1=n->nr,v2=n->r->nr+t->r->nr+1;
    n->l=t->r;t->r=n;
    t->nr=v1;n->nr=v2;
    n=t;
}
void rotright(T *&n)
{
    T *t=n->r;
    int v1=n->nr,v2=n->l->nr+t->l->nr+1;
    n->r=t->l;t->l=n;
    t->nr=v1;n->nr=v2;
    n=t;
}
void balance(T *&n)
{
    if(n->l->P>n->P) rotleft(n);
    else
    if(n->r->P>n->P) rotright(n);
}
void Insert(T *&n,int K)
{
    if(n==nil)
    {
        n=new T(K,Rand(),1,nil,nil);
        return ;
    }
    if(n->K>K) Insert(n->l,K);
    else
    if(n->K<K) Insert(n->r,K);
    n->nr=n->l->nr+n->r->nr+1;
    balance(n);
}
void Erase(T *&n,int K)
{
    if(n->K>K) Erase(n->l,K);
    else
    if(n->K<K) Erase(n->r,K);
    else
    if(n->K==K)
    {
        if(n->l==nil&&n->r==nil){delete n;n=nil;}
        else
        {
            if(n->l->P>n->r->P) rotleft(n);
            else rotright(n);
            Erase(n,K);
        }
    }
    if(n!=nil) n->nr=n->l->nr+n->r->nr+1;
}
void Query(T *&n,int Poz)
{
    if(n->l->nr+1==Poz){ras=n->K;return ;}
    else
    if(n->l->nr>=Poz) Query(n->l,Poz);
    else Query(n->r,Poz-n->l->nr-1);
}
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d",&n);
srand(time(0));
nil=new T(0,0,0,NULL,NULL);
R=new T(1,Rand(),1,nil,nil);
for(i=2;i<=n;i++)
    Insert(R,i);
k=2;cate=n;
for(i=1;i<=n;i++)
{
    k+=i-1;if(k%cate==0) k=cate;else k=k%cate;
    //////////////////////////////////////////////////////////
    Query(R,k);
    printf("%d ",ras);
    Erase(R,ras);
    /////////////////////////////////////////////////////////
    cate--;
}
return 0;
}