Pagini recente » Cod sursa (job #63236) | Cod sursa (job #2213747) | Cod sursa (job #2911034) | Cod sursa (job #506181) | Cod sursa (job #2239463)
#include <bits/stdc++.h>
#define inf 2000000000
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int i,j,n,m;
struct nod{
int info;
int nr,height;
nod *st, *dr;
nod(int info, nod *st, nod *dr)
{
this->dr = dr;
this->st = st;
this->info = info;
nr = 0;
height = -1;
}
};
nod *T,*Ts,*Td,*nil;
void upd(nod *&n)
{
n->nr = n->st->nr + n->dr->nr + 1;
n->height = 1 + max(n->st->height, n->dr->height);
}
void rotateleft(nod *&n)
{
nod *x = n->dr;
n->dr = x->st;
upd(n);
x->st = n;
n = x;
upd(n);
}
void rotateright(nod *&n)
{
nod *x = n->st;
n->st = x->dr;
upd(n);
x->dr = n;
n = x;
upd(n);
}
int heavy(nod *&n)
{
return n->st->height - n->dr->height;
}
void balance(nod *&n)
{
upd(n);
if(heavy(n) > 1)
{
if(heavy(n->st) < 0)
rotateleft(n->st);
rotateright(n);
}
else if(heavy(n) < -1)
{
if(heavy(n->dr) > 0)
rotateright(n->dr);
rotateleft(n);
}
}
void insert(nod *&n, int info)
{
if(n == nil)
{
n = new nod(info, nil, nil);
upd(n);
return;
}
if(info > n->info)
insert(n->dr, info);
else
insert(n->st, info);
balance(n);
}
int find_min(nod *&n)
{
int a;
if(n->st == nil)
{
if(n->dr == nil)
{
a = n->info;
delete n;
n = nil;
}
else
{
nod *x = n;
a = n->info;
n = n->dr;
delete x;
}
}
else
{
a = find_min(n->st);
}
balance(n);
return a;
}
void del(nod *&n,int info)
{
if(n == nil)
return;
if(info > n->info)
del(n->dr, info);
else if(info < n->info)
del(n->st, info);
else
{
if(n->st != nil && n->dr != nil)
{
int a = find_min(n->st);
n->info = a;
}
else if(n->st != nil)
{
nod *x = n;
n = n->st;
delete x;
}
else if(n->dr != nil)
{
nod *x = n;
n = n->dr;
delete x;
}
else
{
delete n, n = nil;
return;
}
}
balance(n);
}
void afiseaza(nod *n)
{
if(n == nil)
return;
afiseaza(n->st);
fout << n->info << " ";
afiseaza(n->dr);
}
int find(nod *&n,int k)
{
if(n->st->nr < k)
{
k-=n->st->nr;
if(k == 1)
return n->info;
return find(n->dr, k - 1);
}
return find(n->st, k);
}
int main()
{
T = nil = new nod(0,NULL,NULL);
fin >> n;
for(i = 1 ; i <= n; i++)
{
insert(T,i);
}
int k = 1;
for(i = 1; i <= n; i++)
{
k += i;
k = k %(n - i + 1);
if(k == 0)
k = n-i+1;
j = find(T,k);
fout<<j<<" ";
del(T,j);
k--;
}
return 0;
}