Cod sursa(job #570413)

Utilizator mihai995mihai995 mihai995 Data 3 aprilie 2011 00:31:22
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
using namespace std;

const int N=30001;
int v[3*N],n;

ifstream in("order.in");
ofstream out("order.out");

inline void update(int poz,int st,int dr,int x,int val)
{
	if (st==dr)
	{
		v[poz]=val;
		return;
	}
	int m=(st+dr)>>1;
	if (x<=m)
		update(poz<<1,st,m,x,val);
	else
		update((poz<<1)+1,m+1,dr,x,val);
	v[poz]=v[poz<<1]+v[(poz<<1)+1];
}

inline int query(int poz,int st,int dr,int x,int y)
{
	if (x<=st && y>=dr)
		return v[poz];
	int m=(st+dr)>>1,a=0,b=0;
	if (m>=x)
		a=query(poz<<1,st,m,x,y);
	if (m<y)
		b=query((poz<<1)+1,m+1,dr,x,y);
	return a+b;
}

int bs(int ii,int x)
{
	int i=ii;
	for (int step=1<<16;step;step>>=1)
		if (i+step<=n && query(1,1,n,ii,i+step)<x)
			i+=step;
	return i+1;
}

int main()
{
	int i,x=1,q;
	in>>n;
	for (i=1;i<=n;i++)
		update(1,1,n,i,1);
	for (i=1;i<=n;i++)
	{
		q=query(1,1,n,x,n);
		if (q>=i%(n-i+1))
			x=bs(x,i%(n-i+1));
		else
			x=bs(0,i%(n-i+1)-q);
		out<<x<<" ";
		update(1,1,n,x,0);
	}
	out<<"\n";
	return 0;
}