Cod sursa(job #458718)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 25 mai 2010 22:11:47
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>

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

#define zero(x) ((x^(x-1))&x) 

#define nmax 30100

int n,aib[nmax];

void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
}

void add(int poz, int val)
{
	int i;
	i=poz;
	for (i++;i<nmax;i+=zero(i))
		aib[i]+=val;
}


int query(int poz)
{
	int i;
	i=poz;
	int rez=0;
	for (i++;i;i-=zero(i))
		rez+=aib[i];
	return rez;
}


int cautare(int X)
{
	int i,step;
	step=1<<15;
	//for (step=1;step<=1<<15;step<<=1);
	      for (i=-1;step;step>>=1)
			   if (i+step<n && query(i+step)<X)
				   i+=step;
			   return i+1;
}

void solve()
{
	int i;
	for (i=0;i<n;++i)
		 add(i,1);
	int poz=1,p;
	for (i=0;i<n;++i)
	{
		poz=(poz+i)%(n-i);
		p=cautare(poz+1);
		printf("%d ",p+1);
		add(p,-1);
	}
	
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}