Cod sursa(job #1991038)

Utilizator NomiusNicu Balaban Nomius Data 14 iunie 2017 19:04:37
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>

#define MAX_N 30001

int n;
int crt_place[MAX_N];
int final_place[MAX_N];
int ftree[MAX_N];

void ftree_add(int pos, int val) {
	while (pos <= n) {
		ftree[pos] += val;
		pos += pos & -pos;
	}
}

int ftree_query(int pos) {
	int sum = 0;
	while (pos > 0) {
		sum += ftree[pos];
		pos -= pos & -pos;
	}
	return sum;
}

int bsearch(int val) {
	int l = 1;
	int h = n;
	int mid;

	while (l < h) {
		mid = (l + h) >> 1;

		if (ftree_query(mid) < val)
			l = mid + 1;
		else
			h = mid;
	}

	return l;
}

int main(void) {
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);

	// read data and add 1 to all positions in ftree
	// 1 means it's a free slot. 0 means it's been occupied
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &crt_place[i]);
		ftree_add(i, 1);
	}

	// process the data beginning from the last skier. this last skier is
	// certain of his final position. search for the k-th place and mark it
	// as occupied. then repeat for remaining skiers.
	int final_pos;
	for (int i = n; i > 0; i--) {
		// find the final place of skier i in the fenwick tree with bsearch
		final_pos = bsearch(crt_place[i]);
		final_place[final_pos] = i;
		// make that position 0 (occupied)
		ftree_add(final_pos, -1);
	}

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

	return 0;
}