Cod sursa(job #643430)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 3 decembrie 2011 18:02:01
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <cstdio>

#define file_in "order.in"
#define file_out "order.out"

#define lsb(x) ((x)&(-(x)))

int Aib[35000],N;

void add(int poz, int val){
	
	int i;
	for (i=poz;i<=N;i+=lsb(i))
		 Aib[i]+=val;
}

int sol(int poz){
	int i,ans=0;
	for (i=poz;i>=1;i-=lsb(i))
		 ans+=Aib[i];
	return ans;
}

int cauta(int k){
	
	int i,step;
	for (step=1;step<=N;step<<=1);
	for (i=0;step;step>>=1)
		 if (i+step<=N){
			 int X=sol(i+step);
			 if (k>=X)
				 i+=step;
		 }
	return i+1;		 
}	
	

int main(){
	
	int i,j,NN,X,p;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &N);
	for (i=1;i<=N;++i)
		 add(i,1);
	
	j=1;
	for (i=0;i<N;++i)
	{
		j=(j+i)%(N-i);
		p=cauta(j+1);
		printf("%d ",p-1);
		add(p,-1);
	}
	
	return 0;
	
}