Cod sursa(job #549028)

Utilizator loginLogin Iustin Anca login Data 8 martie 2011 08:49:43
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
# include <fstream>
# include <iostream>
# include <vector>
# define DIM 30003
using namespace std;
int n, a[4*DIM], r=1;

void init (int k, int st, int dr, int p)
{
	if (st==dr)
	{
		a[k]=1;
		return;
	}
	int mij=(st+dr)/2;
	if (p<=mij)init(2*k, st, mij, p);
	else init (2*k+1, mij+1, dr, p);
	a[k]=a[2*k]+a[2*k+1];
}

int nmr (int k, int st, int dr, int i, int j)
{
	if (st>=i && dr<=j)
		return a[k];
	int mij=(st+dr)/2, a=0, b=0;
	if (i<=mij)a=nmr(2*k, st, mij, i, j);
	if (j>mij)b=nmr(2*k+1, mij+1, dr, i, j);
	return a+b;
}	

void query (int k, int st, int dr, int p)
{
	if (st==dr)
	{
		a[k]=0;
		r=st;
		return;
	}
	int mij=(st+dr)/2;
	if (a[2*k]>=p)query(2*k, st, mij, p);
	else query(2*k+1, mij+1, dr, p-a[2*k]);
	a[k]=a[2*k]+a[2*k+1];
}

int main ()
{
	ifstream fin ("order.in");
	ofstream fout ("order.out");
	fin>>n;
	for(int i=1;i<=n;++i)
		init(1, 1, n, i);
	int s, nr, l;
	for(int i=1;i<=n;++i)
	{
		s=nmr(1, 1, n, 1, r);
		nr=nmr(1, 1, n, r+1, n);
		if (nr>=i)
			l=s+i;
		else
		{
			l=(i-nr)%a[1];
			if (l==0)
				l=a[1];
		}
		query(1, 1, n, l);
		fout<<r<<" ";
	}
	return 0;
}