Cod sursa(job #236326)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 27 decembrie 2008 11:13:45
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 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,A[1<<15];

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

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

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

int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	scanf("%d",&N);
	
	int p(1),poz;
	FOR(i,1,N)
		for(poz = i,A[i] = 1;!(poz&1);poz >>= 1,A[i] <<= 1); 
	
	for(int i=0;i<N;++i)
	{
		poz = find( (p = (p+i) % (N-i)) + 1);
		update(poz,-1);
		printf("%d ",poz);
	}	
	
	return 0;
}