Cod sursa(job #217451)

Utilizator andrei.12Andrei Parvu andrei.12 Data 28 octombrie 2008 17:25:33
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>

#define lg 100000

int n, p, gs, x, i, q[lg], init[lg];

void cstr(int st, int dr, int poz){
	if (st == dr){
		init[st] = poz;
		return ;
	}

	int y = (st + dr) / 2;
	cstr(st, y, 2*poz); cstr(y+1, dr, 2*poz+1);
}
void find(int st, int dr, int poz){
	if (p > dr)
		return ;
	if (p <= st){
		if (dr - st + 1 - q[poz] < x){
			x -= dr - st + 1 - q[poz];
			return ;
		}
		if (st == dr){
			gs = st;
			return ;
		}
	}
	
	int y = (st + dr) / 2;
	find(st, y, 2*poz);

	if (!gs)
		find(y+1, dr, 2*poz+1);
}
void update(int poz){
	int pp = init[poz];

	for (; pp; pp /= 2)
		q[pp] ++;
}

int main()
{
	freopen("order.in", "rt", stdin);
	freopen("order.out", "wt", stdout);

	scanf("%d", &n);
	cstr(1, n, 1);

	gs = 1;
	for (i = 1; i <= n; i ++){
		p = gs+1;

		x = i; gs = 0;
		find(1, n, 1);
		
		if (!gs){
			x = x % (n-i+1); if (!x) x = (n-i+1);
			p = 1;
			find(1, n, 1);
		}

		printf("%d ", gs);
		update(gs);
	}
	printf("\n");

	return 0;
}