Cod sursa(job #233975)

Utilizator cotofanaCotofana Cristian cotofana Data 19 decembrie 2008 20:00:44
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>
#define dim 30001

int n, aib[dim];

void update(int p, int val)
{
	p++;
	while (p<=n)
	{
		aib[p]+=val;
		p+=p&(-p);
	}
}

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

int binary_search(int val)
{
	int i, step=1;
	while (step<n) step<<=1;
	for (i=-1; step; step>>=1)
		if (i+step < n && query(i+step)<val)
			i+=step;
	return i+1;
}

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