Cod sursa(job #614352)

Utilizator dacyanMujdar Dacian dacyan Data 6 octombrie 2011 10:27:54
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <vector>
#define DIM 30001
using namespace std;

ofstream fout("order.out");

int n, m;
int a[DIM];
int G[4*DIM]; 
int x, y, poz, val, nr, X, N;


void Build(int, int, int);
void Query(int, int, int);  // care este a X- a pozitie nearsa
void Query2(int, int, int); // cate poz nearse sunt pana la poz
void Update(int, int, int);
void Read();
void Write();


int main()
{
	ifstream fin("order.in");
	fin >> n;
	fin.close();
	
	Build(1,1,n);
	
	fout << "2 ";

	poz = 2;
	Update(1, 1, n); // ard valoarea 1
	
	for (int r = 2; r <= n; ++r)
	{
		nr = 0;
		x = 1; y = poz;
		Query2(1, 1, n); //cate pozitii nearse sunt pana la poz
		
		X = nr + r; // a X-a pozitie nearsa(X <= n) incepand de la 1
		while (X > G[1]) X -= G[1];
		
		poz = 0;
		Query(1,1,n); // caut a X-a pozitie nearsa
		fout << poz << ' ';
		Update(1,1,n); // o ard
	}
	fout << '\n';
	
	fout.close();
	return 0;
}

void Build (int nod, int st, int dr)
{
	if (st == dr)
	{
		G[nod] = 1;
		return;
	}
	int mij = (st + dr) / 2;
	Build(2 * nod, st, mij);
	Build(2 * nod + 1, mij + 1, dr);
	G[nod] = G[2*nod] + G[2*nod+1];
}

void Update(int nod, int st, int dr)
{
	if (st == dr)
	{
		G[nod] = 0;
		return;
	}
	int mij = (st + dr) / 2;
	if (poz <= mij) Update(2*nod, st, mij);
	else Update(2*nod+1, mij + 1, dr);
	G[nod] = G[2*nod] + G[2*nod+1];
}

void Query(int nod, int st, int dr)
{
	if (st == dr)
	{
		poz = st;
		return;
	}
	int mij = (st + dr) / 2;
	if (X <= G[2*nod]) Query(2*nod, st, mij);
	else
	{
		X -= G[2*nod];
		Query(2*nod+1, mij+1, dr);
	}
}


void Query2(int nod, int st, int dr)
{
	if (x <= st && dr <= y)
	{
		nr += G[nod];
		return;
	}
	int mij = (st + dr) / 2;
	if (x <= mij) Query2(2*nod, st, mij);
	if (y > mij) Query2(2*nod+1, mij+1, dr);
}