Cod sursa(job #216302)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 23 octombrie 2008 20:54:20
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>

#define mij (((st) + (dr)) / 2)
#define fiu1 (nod * 2)
#define fiu2 ((nod * 2) + 1)

const int A_MAX = (1 << 18);

int aint[A_MAX];

void constr(int nod, int st, int dr)
{
	if (st == dr) aint[nod] = 1;
	else {
		constr(fiu1, st, mij);
		constr(fiu2, mij + 1, dr);
		aint[nod] = aint[fiu1] + aint[fiu2];
	}
}

void update(int nod, int st, int dr, int poz)
{
	if (st == dr) aint[nod] --;
	else {
		if (poz <= mij) update(fiu1, st, mij, poz);
		else update(fiu2, mij + 1, dr, poz);

		aint[nod] = aint[fiu1] + aint[fiu2];
	}
}

int find(int nod, int st, int dr, int K)
{
	if (st == dr) return st;
	else {
		if (K <= aint[fiu1]) find(fiu1, st, mij, K);
		else find(fiu2, mij + 1, dr, K - aint[fiu1]);
	}
}

int main()
{
	freopen("order.in", "r", stdin);
#ifndef _SCREEN_
	freopen("order.out", "w", stdout);
#endif

	int N;
	scanf("%d\n", &N);
	constr(1, 1, N);

	printf("2 ");
	update(1, 1, N, 2);

	int K, last = 2, ram = N - 1, care;
	for (int i = 2; i <= N; i ++) {
		K = (last + i - 1) % ram;
		if (K == 0) K = ram;
	//	printf("K = %d\n", K);

		care = find(1, 1, N, K);
		update(1, 1, N, care);
	//	printf("\n\n");

		printf("%d ", care);
		last = K;
		ram --;
	}

	return 0;
}