Pagini recente » Cod sursa (job #3204642) | Cod sursa (job #831142) | Rating Raducu Ioan Stefan (Neuer) | Cod sursa (job #1568828) | Cod sursa (job #456230)
Cod sursa(job #456230)
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define getc(T) (T) -> cnt = (T) -> l -> cnt + (T) -> r -> cnt + 1
typedef struct nod {
int key, p, cnt;
nod *l, *r;
nod(){}
nod(int key, int p, int cnt, nod *l, nod *r) {
this -> key = key;
this -> p = p;
this -> cnt = cnt;
this -> l = l;
this -> r = r;
}
} *treap;
treap R, nil;
int N;
void rotleft(treap &T) {
treap aux = T -> l;
T -> l = aux -> r;
aux -> r = T;
getc(T);
getc(aux);
T = aux;
}
void rotright(treap &T) {
treap aux = T -> r;
T -> r = aux -> l;
aux -> l = T;
getc(T);
getc(aux);
T = aux;
}
void balance(treap &T) {
if(T -> l -> p > T -> p)
rotleft(T);
if(T -> r -> p > T -> p)
rotright(T);
getc(T);
}
void insert(treap &T, int key) {
if(T == nil) {
T = new nod(key, rand()+1, 1, nil, nil);
return;
}
if(key < T -> l -> key)
insert(T -> l, key);
else
insert(T -> r, key);
balance(T);
}
void erase(treap &T, int key) {
if(T == nil) return;
if(key < T -> key)
erase(T -> l, key);
else if(key > T -> key)
erase(T -> r, key);
else {
if(T -> l == nil && T -> r == nil) {
delete T;
T = nil;
return;
}
else {
(T -> l -> p > T -> r -> p)? rotleft(T) : rotright(T);
erase(T, key);
}
}
getc(T);
}
int search(treap &T, int val) {
if(T == nil) return 0;
if(T -> l -> cnt == val-1)
return T -> key;
if(val <= T -> l -> cnt)
return search(T -> l, val);
else
return search(T -> r, val - T -> l -> cnt - 1);
}
void init() {
srand(time(NULL));
R = nil = new nod(0, 0, 0, NULL, NULL);
}
int main() {
freopen("order.in","rt",stdin);
freopen("order.out","wt",stdout);
init();
scanf("%d", &N);
for(int i = 1; i <= N; ++i)
insert(R, i);
int p = 1;
for(int i = 1; i <= N; ++i) {
int n = N-i+1;
p = (p+i)%n;
if(p == 0) p = n;
int v = search(R, p);
printf("%d ", v);
erase(R, v);
--p;
}
}