Cod sursa(job #614230)

Utilizator dacyanMujdar Dacian dacyan Data 5 octombrie 2011 21:24:28
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 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;
int runda;

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
	N = n - 1;
	for (runda = 2; runda <= n; ++runda)
	{
		int r;
		if (runda > n) r = runda % n;
		else r = runda;
		
		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
		if (N == 1) X = 1; // daca N este 1 - a ramas o singura pozitie nearsa
		else
			if (X > N) X %= N;
		
		
		poz = 0;
		Query(1,1,n); // caut a X-a pozitie nearsa
		fout << poz << ' ';
		Update(1,1,n); // o ard
		N--;
	}
	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);
}