Cod sursa(job #236308)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 27 decembrie 2008 10:02:33
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
using namespace std;

#include <bitset>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define bit(x) ((x)&(x-1))^(x)

int N,poz;
int A[1<<15];

void update(int x)
{
	for(int i=x;i<=N;i += bit(i) )
		++A[i];
}	

int querry(int x,int y)
{  
	int sum(0);
	for(int i=y;i>=1;i -= bit(i) )
		sum += A[i];
	for(int i=x-1;i>=1;i -= bit(i) )
		sum -= A[i];
	return y-x+1-sum;
}

int find(int K)
{
	int m,step(1<<15);
	int up = querry(poz+1,N);
	int down = querry(1,poz);
	
	if(K <= up)
	{
		for(m=poz+1;step;step >>= 1)
			if(m+step <= N && querry(poz+1,m+step-1) < K)
				m += step;
		return m;
	}	
	if(K <= up + down)
	{	
		for(m=1;step;step >>= 1)
			if(m+step <= poz && querry(1,m+step-1) + up < K)
				m += step;
		return m;
	}
	if(K % (up+down))
		return find(K % (up+down));
	return find(up+down);
}

int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	scanf("%d",&N);
	
	poz = 1;
	FOR(i,1,N)
	{
		poz = find(i);
		update(poz);
		printf("%d ",poz);
	}	
	
	return 0;
}