Cod sursa(job #456230)

Utilizator Mishu91Andrei Misarca Mishu91 Data 15 mai 2010 00:19:22
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#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;
	}
}