Cod sursa(job #736430)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 18 aprilie 2012 16:55:43
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
using namespace std;

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

const int maxn=30005;
int i,N;
int A[maxn],C[maxn],P[maxn];

void update(int poz, int val) {
	while(poz<=N) {
		A[poz]+=val;
		poz+=(poz & (-poz));
	}
}

int suma(int poz) {
	int S=0;
	while(poz) {
		S+=A[poz];
		poz-=(poz & (-poz));
	}
	return S;
}

int cb(int x) {
	int st,m,dr,s,poz=N;
	st=1; dr=N; m=(st+dr)/2;
	while(st<=dr) {
		s=suma(m);
		if(s<x) st=m+1;
		else {
			dr=m-1;
			if(s==x) poz=min(poz,m);
		}
		m=(st+dr)/2;
	}
	return poz;
}

int main() {
	fin >> N;
	for(i=1;i<=N;i++) fin >> C[i];
	
	for(i=1;i<=N;i++) 
		update(i,1);
	
	for(i=N;i;i--) {
		int p= cb(C[i]);
		P[p]=i;
		update(p,-1);
	}
	for(i=1;i<=N;i++) fout << P[i] << '\n';
}