Pagini recente » Cod sursa (job #1851957) | Cod sursa (job #556407) | Cod sursa (job #3287478) | Cod sursa (job #195699) | Cod sursa (job #400698)
Cod sursa(job #400698)
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<vector>
#define oo 0x3f3f3f3f //infinit
using namespace std;
struct nod{
int v,p,sub;
nod *r,*l;
};
typedef nod* treap;
treap R,nil;
ofstream fout("order.out");
ifstream fin("order.in");
inline void init()
{ nil=new nod;
nil->v=nil->p=-oo;
nil->sub=0;
nil->l=nil;
nil->r=nil;
R=nil;
}
inline void getsub(treap&n)
{if(n==nil) return;
n->sub=1;
if(n->l!=nil) n->sub+=n->l->sub;
if(n->r!=nil) n->sub+=n->r->sub;
}
void rright(treap &n)
{treap t=n->r;
n->r=t->l;
t->l=n;
getsub(n);
getsub(t);
n=t;
}
void rleft(treap &n)
{treap t=n->l;
n->l=t->r;
t->r=n;
getsub(n);
getsub(t);
n=t;
}
void insert(treap &n,int v)
{if(n==nil)
{n=new nod;
n->l=n->r=nil;
n->v=v;
n->sub=1;
n->p=rand()-1;
return;
}
if(n->v <v)
{insert(n->r,v);
if(n->r->p > n->p)
rright(n);
}
if(n->v >v)
{insert(n->l,v);
if(n->l->p > n->p)
rleft(n);
}
getsub(n);
}
void sterge(treap &n,int v)
{
if(n==nil) return;
if(n->v < v) sterge(n->r,v);
if(n->v > v) sterge(n->l,v);
if(n->v==v)
{
if(n->l==nil && n->r==nil)
{
delete n;
n=nil;
return;
}
else
if(n->l->p > n->r->p)
rleft(n);
else
rright(n);
sterge(n,v);
}
getsub(n);
}
int fiind(treap &n,int k) /// nu stiu de ce nu merge asta:-?? ca daca avem 1 2 3 ar trebui sa mearga
{if(n==nil) return 0;
if(k==n->sub) return n->v;
if(k<n->sub) return fiind(n->l,k);
if(k>n->sub) return fiind(n->r,k-(n->sub));
return 0;
}
inline int findk(treap n, int k) ///
{
if(n==nil) return 0;
if(k==n->l->sub+1) return n->v;
if(k<n->l->sub+1) return findk(n->l, k);
else return findk(n->r, k-(n->l->sub+1));
return 0;
}
int main()
{ int namb,i,k,p,fifi;
srand(time(0));
init();
ifstream fin("order.in");
fin>>namb;
fin.close();
for(i=1;i<=namb;i++)
insert(R,i);
p=1;
k=1;
while(namb)
{p=((p+k)-1)%namb+1; // pentru ca astfel restul va fi mereu in range-ul [1...NAMB]=> great succes !!!:D
fifi=findk(R,p);
fout<<fifi<<" ";
sterge(R,fifi);
k++;
namb--;
p=p-1;
}
fin.close();
fout.close();
return 0;
}