Cod sursa(job #713940)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 15 martie 2012 10:19:22
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<iostream>
#include<fstream>
using namespace std;

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

int n,aib[34000],x[34000],sol[34000];

inline void add(int poz, const int &val) {
	
	while(poz<=n) {
		
		aib[poz]+=val;
		poz+=poz&(-poz);
	}
}

inline int s(int poz) {
	int s=0;
	
	while(poz) {
		
		s+=aib[poz];
		poz-=poz&(-poz);
	}
	return s;
}

inline int q(int a, int b) {
	a = (a-1)%n + 1;
	b = (b-1)%n + 1;
	
	if(b>=a)
		return s(b) - s(a-1);
	return q(b,n) + s(a);
}

int main() {
	int i,j,pas;
	
	in >> n;
	
	for(i=1;i<=n;++i) {
		add(i,1);
		in >> x[i];
	}
	
	for(i=n;i!=0;--i) {
		pas=1<<16;
		
		for(j=0;pas!=0;pas>>=1)
			if(j+pas<=n && q(1,j+pas)<x[i])
				j+=pas;
		++j;
		
		sol[j] = i;
		add(j,-1);
	}
	
	for(i=1;i<=n;++i)
		out << sol[i] << '\n';
	
	return 0;
}