Cod sursa(job #1738253)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 6 august 2016 10:47:15
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#define MAX 30005
#define zeros(x) (((x - 1) ^ x) & x)

int n, p[MAX], a[MAX], pos[MAX];

void update(int x, int val){
	for(; x <= n; x += zeros(x))
		a[x] += val;
}

int compute(int x){
	int sum = 0;
	for(; x; x -= zeros(x))
		sum += a[x];
	return sum;
}

int search(int x){
	int s = 0, d = n + 1;
	while(s < d - 1){
		int m = (s + d) / 2;
		int val = compute(m);
		if(val < x)
			s = m;
		else
			d = m;
	}
	return d;
}

int main(){
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		scanf("%d", &p[i]);
		update(i, 1);
	}

	for(int i = n; i; --i){
		int res = search(p[i]);
		pos[res] = i;
		update(res, -1);
	}

	for(int i = 1; i <= n; ++i)
		printf("%d\n", pos[i]);
	return 0;
}