Cod sursa(job #529274)

Utilizator feelshiftFeelshift feelshift Data 4 februarie 2011 16:59:49
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
// http://infoarena.ro/problema/schi
#include <fstream>
using namespace std;

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

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

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

void add(int location,int value);
int query(int right);
int search(int left,int right);

int cautare(int X)
{
	int h,step;
	
	for (step=1;step<=lenght;step<<=1); 
	step>>=1;
	for (h=lenght;step;step>>=1)
		 if (h-step>=1 && query(h-step)>=X)
				  h-=step;
	return h;
}	

int main() {
	int position;

	in >> lenght;

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

	for(i=lenght;i>=1;i--) {
		//position = search(1,lenght);
		position = cautare(person[i]);
		place[position] = i;
		add(position,-1);
	}

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

	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 left,int right) {
	int middle = (left + right) / 2;
	int answer = query(middle);

	if(answer == person[i])
		//if(query(middle-1) != query(middle))
			return middle;
		//else
			//return search(left,middle-1);
	else
		if(answer > person[i])
			return search(left,middle-1);
		else
			return search(middle+1,right);
}