Cod sursa(job #1419704)

Utilizator razvan3895Razvan-Mihai Chitu razvan3895 Data 16 aprilie 2015 10:53:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <string>
#include <stdio.h>
#include <iostream>
using namespace std;


int *AIB, *v, cp, m, maxim = 1, *clasament, step, certain;

void update(int val, int poz) {
	for(int i = poz; i <= maxim; i += (i & (-i)))
		AIB[i] += val;
}

int value(int poz) {
	int rez = 0;
	for(int i = poz; i > 0; i -= (i & (-i)))
		rez += AIB[i];
	return rez;
}

int find(int value) {
	int step = maxim, certain = -1;
	for(int j = 0; step; step >>= 1) {
		if(j + step < maxim && AIB[j + step] <= value) {
			if(AIB[j + step] == value) {
				certain = j + step;
				continue;						
			}
			value -= AIB[j + step], j += step;
		}						
	}
	return certain;
}

int main() {
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	int sol;
	scanf("%d", &m);
	for(cp = m; cp >>= 1; maxim <<= 1);
	maxim <<= 1;
	AIB = new int[maxim + 1];
	v = new int[m + 1];
	clasament = new int[m + 1];

	for(int i = 1; i <= m; ++i) {
		scanf("%d", &v[i]);
		update(1, i);
	}

	for(int i = m; i >= 1; --i) {
		sol = find(v[i]);
		update(-1, sol);
		clasament[sol] = i;
	}

	for(int i = 1; i <= m; ++i) {
		printf("%d\n", clasament[i]);
	}

	

	delete[] clasament;
	delete[] v;
	delete[] AIB;
	return 0;
}