Cod sursa(job #179416)

Utilizator anoukAnca Dumitrache anouk Data 15 aprilie 2008 21:39:55
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <iostream>
#define DIM (1<<15)
#define pivot ((st + dr)>>1)
using namespace std;

int N, A[DIM<<1], V[DIM], S[DIM], P;

void Build(int nod, int st, int dr)
{
	if (st == dr)
	{
		A[nod] = 1;
		return;
	}
	Build(2 * nod, st, pivot);
	Build(2 * nod + 1, pivot + 1, dr);
	A[nod] = A[2 * nod] + A[2 * nod + 1];
}

void Update(int nod, int st, int dr)
{
	if (st == dr)
	{
		A[nod]--;
		return;
	}
	if (P <= pivot) Update(2 * nod, st, pivot);
	else		Update(2 * nod + 1, pivot + 1, dr);
	A[nod] = A[2 * nod] + A[2 * nod + 1];
}

int Query(int nod, int st, int dr, int nr)
{
	if (st == dr) return st;
	if (nr <= A[2 * nod]) return Query(2 * nod, st, pivot, nr);
	else                  return Query(2 * nod + 1, pivot + 1, dr, nr - A[2 * nod]);
}

int main()
{
	FILE *fin = fopen("schi.in", "r");
	FILE *fout = fopen("schi.out", "w");

	fscanf(fin, "%d", &N);
	for (int i = 1; i <= N; i++)
		fscanf(fin, "%d", V+i);
	Build(1, 1, N);
	for (int i = N; i > 0; i--)
	{
		P = Query(1, 1, N, V[i]);
		S[P] = i;
		//cout << i << " " << P; cin.get();
		Update(1, 1, N);
	}
	for (int i = 1; i <= N; i++)
		fprintf(fout, "%d\n", S[i]);

	fclose(fin);
	fclose(fout);
	return 0;
}