Cod sursa(job #575941)

Utilizator mihai995mihai995 mihai995 Data 8 aprilie 2011 22:59:15
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <cstdio>
using namespace std;

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

ifstream in("order.in");

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 (y<x)
		return 0;
	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<<13;step;step>>=1)
		if (i+step<=n && query(1,1,n,ii,i+step)<x)
			i+=step;
	return i+1;
}

inline void greedy_query(int poz,int st,int dr)
{
	if (v[poz]<=val)
	{
		val-=v[poz];
		if (pmax<dr)
			pmax=dr;
		return;
	}
	if (st==dr)
		return;
	int m=(st+dr)>>1,S=poz<<1,D=(poz<<1)+1;
	if (v[S]>val)
		greedy_query(S,st,m);
	else
	{
		val-=v[S];
		if (pmax<m)
			pmax=m;
		greedy_query(D,m+1,dr);
	}
}

inline int greedy(int V)
{
	val=V-1;
	pmax=0;
	greedy_query(1,1,n);
	return pmax+1;
}	

int main()
{
	freopen("order.out","w",stdout);
	int i,x=1,q,p;
	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);
		p=(i-1)%(n-i+1)+1;
		if (q>=p)
			x=greedy(p+query(1,1,n,1,x));
		else
			x=greedy(p-q);
		printf("%d ",x);
		update(1,1,n,x,0);
	}
	printf("\n");
	return 0;
}