Cod sursa(job #272218)

Utilizator codrinCodrin LACHE codrin Data 6 martie 2009 17:02:10
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>

#define Nmax 30005

int n;
int v[Nmax];
int seg[4*Nmax];
int rez[Nmax];

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

void update(int poz, int st, int dr, int val)
{
	if (st == dr)
	{
		seg[poz] = 0;
		return;
	}
	int m = (st+dr)/2;
	
	if (val <= m) update(poz*2, st, m, val);
	else update(poz*2+1, m+1, dr, val);
	
	seg[poz] = seg[poz*2] + seg[poz*2+1];
}

int query(int poz, int st, int dr, int val)
{
	if (st == dr) return st;
	int m = (st+dr)/2;
	
	if (seg[poz*2] < val) return query(poz*2+1, m+1, dr, val-seg[poz*2]);
	return query(poz*2, st, m, val);
}

void constr(int poz, int st, int dr)
{
	seg[poz] = dr-st+1;
	
	int m = (st+dr)/2;
	if (st < dr)
	{
		constr(poz*2, st, m);
		constr(poz*2+1, m+1, dr);
	}
}

void solve()
{
	int i, j;
	int aux;
	
	constr(1, 1, n);
	for (i = n; i; --i)
	{
		aux = query(1, 1, n, v[i]);
		rez[aux] = i;
		update(1, 1, n, aux);
	}
}

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

int main()
{
	readdata();
	solve();
	writedata();
	return 0;
}