Cod sursa(job #856309)

Utilizator aladinaladin aladinn aladin Data 16 ianuarie 2013 11:27:18
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#define lsb(x) x&(-x)
int n,aib[30009];

void update(int poz)
{
	for (;poz<=n;poz+=lsb(poz))
		++aib[poz];
}
	
void del(int poz)
{
	for (;poz<=n;poz+=lsb(poz))
		--aib[poz];
}

int getnr(int poz)
{int nr=0;
	for (;poz>0;poz-=lsb(poz))
		nr+=aib[poz];
 return nr;
}

int search(int poz)
{
	int x=1,y=n,z,rez=n;
	while (x<=y)
	{
		z=(x+y)/2;
		int nr=getnr(z);
		if (nr>=poz)
			rez=z,y=z-1; else
				x=z+1;
	}
	return rez;
}
	

int getnewpoz(int poz,int count, int NrLeft)
{
	int nrstanga=getnr(poz),nr_caut=count;
	if (count>NrLeft)
		nr_caut=count-NrLeft*((count-1)/NrLeft);
	if (nr_caut>NrLeft-nrstanga)
		return search(nr_caut-NrLeft+nrstanga); else
			return search(nr_caut+nrstanga);
}
		


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