Cod sursa(job #828430)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 3 decembrie 2012 19:22:34
Problema Distincte Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
using namespace std;

int v[100000],a[100000],i,n,m,p,k;

void update(int k,int val)
{
	int i;
	for (i=k;i<=m;i=(i | (i-1))+1)
		v[i]+=val;
}

int query(int k)
{
	int i,s=0;
	for (i=k;i>0;i=i & (i-1))
		s+=v[i];
	return s;
}

int search(int k)
{
	int i,t=0;
	for (i=m;i>=1;i/=2)
		if ((v[i/2+t]<=k) && (i/2+t<=n))
		{
			k-=v[i/2+t];
			t+=i/2;
		}
	return t;
}

int main()
{
	ifstream f("order.in");
	ofstream g("order.out");
	f >> n;i=n;m=1;
	while (i>0)
	{
		i/=2;
		m*=2;
	}
	for (i=1;i<=n;i++)
		update(i,1);
	p=1;k=1;
	for (i=1;i<=n;i++)
	{
		p=search((k+i-1)%(n-i+1)+1);
		while (a[p]==1)
		{
			p--;
			if (p==0)
				p=n;
		}
		g << p << ' ';
		update(p,-1);
		a[p]=1;
		k=query(p);
	}
	return 0;
}