Cod sursa(job #532860)

Utilizator feelshiftFeelshift feelshift Data 12 februarie 2011 17:19:31
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
// http://infoarena.ro/problema/schi
// rezolvata folosind arbori indexati binar (http://infoarena.ro/aib)
#include <fstream>
using namespace std;

#define maxSize 30002
#define zeros(x) ( (x ^ (x - 1)) & x )

int lenght;
int AIB[maxSize],person[maxSize],place[maxSize];

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

void add(int location,int value);	// adauga la position "location" valoarea "value"
int query(int right);	// returneaza suma subsecventei [1,right]
int search(int toBeFound);	// cautare binara

int main() {
	int position;

	in >> lenght;

	for(int i=1;i<=lenght;i++) {
		in >> person[i];	// locul ocupat in clasamentul intermediar
		add(i,1);
	}

	// se iau toti concurentii in ordine inversa
	for(int i=lenght;i>=1;i--) {
		// se determina pozitia acestuia in clasament (cautare binara)
		position = search(person[i]);
		// concurentul respectiv va ocupa pozitia aceasta
		place[position] = i;
		// aceasta pozitie este stearsa din pozitiile disponibile
		add(position,-1);
	}

	for(int i=1;i<=lenght;i++)
		out << place[i] << "\n";

	in.close();
	out.close();

	return (0);
}

void add(int location,int value) {
	for(int k=location;k<=lenght;k=k+zeros(k))
		AIB[k] = AIB[k] + value;
}

int query(int right) {
	int value = 0;

	for(int k=right;k>0;k=k-zeros(k))
		value = value + AIB[k];

	return value;
}

int search(int toBeFound) {
	int left = 1,right = lenght;
	int middle,answer = 0;

	for(;;) {
		middle = (left + right) / 2;
		answer = query(middle);

		if(answer == toBeFound)
			if(answer == query(middle-1))	// daca exista o pozitie mai "mica" cu aceeasi valoare a sumei
				right = middle-1;
			else
				return middle;
		else
			if(answer > toBeFound)
				right = middle-1;
			else
				left = middle+1;
	}
}