Cod sursa(job #46162)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 2 aprilie 2007 13:14:15
Problema Schi Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>

const int NMAX = 1 << 15;

int N;
int AIB[NMAX], P[NMAX];
int A[NMAX], next[NMAX];

int parinte(int u) {
	if (u != next[u])
		next[u] = parinte(next[u]);
	return next[u];
}

void update(int poz, int v) {
	for (; poz <= N; poz += poz & ~(poz - 1))
		AIB[poz] += v;
}

int query(int poz) {
	int s;
	for (s = 0; poz > 0; poz -= poz & ~(poz - 1))
		s += AIB[poz];
	return s;
}

int main(void) {

	FILE *fin = fopen("schi.in", "rt");
	FILE *fout = fopen("schi.out", "wt");

	int i, u;

	fscanf(fin, " %d", &N);

	for (i = 1; i <= N; ++i) {
		fscanf(fin, " %d", A + i);
		next[i] = i;
	}

	for (i = N; i; --i) {
		u = A[i];

		u += query(u);
		update(u, 1);
		u = parinte(u);
		P[u] = i; next[u] = u + 1;
	}

	for (i = 1; i <= N; ++i)
		fprintf(fout, "%d\n", P[i]);

	fclose(fin);
	fclose(fout);

	return 0;
}