Cod sursa(job #533056)

Utilizator cosmyoPaunel Cosmin cosmyo Data 12 februarie 2011 22:49:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<cstdio>
using namespace std;
const int N = 30005;
int n, v[N * 4], ind[N], K, p;

void build(int st, int dr, int poz) {
	int x = (st +dr) / 2;
	if(st == dr) {
		ind[st] = poz; 
		return ;
	}
	build(st, x, poz * 2);
	build(x + 1, dr, poz * 2 + 1);
}

void update(int poz, int val) {
	int x = ind[poz];
	v[x] += val;
	for(x /= 2; x; x /= 2)
		v[x] = v[2 * x] + v[2 * x + 1];
}

int query(int st, int dr, int poz) {
	if(st == dr)
		return st;
	int x = (st + dr) / 2;
	if(p + v[poz * 2] >= K)
		return	query(st, x, poz * 2);
	else {
		p += v[poz * 2];
		return query(x + 1, dr, poz * 2 + 1);
	}
}

int main() {
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
	int i;
	scanf("%d ", &n);

	build(1, n, 1);

	for(i = 1; i <= n; ++i)
		update(i, 1);
	K = 1;
	int N = n, x;
	for(i = 1; i <= N; ++i) {
		K = (K + i) % n;	
	//	printf("%d ", K);
		if(K == 0)
			K = n;
		p = 0;
		x = query(1, N, 1);
		printf("%d ", x);
		update(x, -1);
		--n;
		--K;
		if(K == 0)
			K = n;

	}

	printf("\n");

	return 0;
}