Cod sursa(job #68)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 4 decembrie 2006 21:49:14
Problema Order Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <stdio.h>

#define MAXN 30005

int N;
int aib[MAXN];

int query(int p)
{
	int rez = 0;
	for (p++; p; p -= (p ^ (p - 1)) & p)
		rez += aib[p];
	return rez;
}

void update(int p, int val)
{
	for (p++; p < MAXN; p += (p ^ (p - 1)) & p)
		aib[p] += val;
}

int binsearch(int k)
{
	int i, step = 1 << 15;
	for (i = -1; step; step >>= 1)
		if (i + step < N && query(i + step) < k)
			i += step;
	return i + 1;
}

int main()
{
	freopen("order.in", "rt", stdin);
	freopen("order.out", "wt", stdout);
	scanf("%d", &N);
	int p, i, poz;
	for (i = 0; i < N; i++)
		update(i, 1);
	for (p = 1, i = 0; i < N; i++)
	{
		p = (p + i) % (N - i);
		poz = binsearch(p + 1);
		if (i) printf(" ");
		printf("%d", poz + 1);
		update(poz, -1);
	}
	printf("\n");
	return 0;
}