Cod sursa(job #644353)

Utilizator marius21Petcu Marius marius21 Data 6 decembrie 2011 10:12:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>

#define zeros(x) (((x-1) ^ x) & x)

int a[30001];
int aib[30001];
int n;

void read()
{
	FILE * fin = fopen("schi.in","r");
	fscanf(fin,"%d",&n);
	for (int i = 0; i < n; i++)
		fscanf(fin,"%d",a+i);
	fclose(fin);
}

void write()
{
	FILE * fout = fopen("schi.out","w");
	for (int i = 0; i < n; i++)
		aib[a[i]] = i+1;
	for (int i = 1; i <= n; i++)
		fprintf(fout,"%d\n",aib[i]);
	fclose(fout);
}

void aib_update(int i, int val)
{
	for (; i<=n; i+=zeros(i))
		aib[i]+=val;
}

int aib_query(int i)
{
	int r = 0;
	for (; i; i-=zeros(i))
		r+=aib[i];
	return r;
}

int binary_search(int val)
{
	int step,i;
	for (step = 1; step <= n; step <<= 1);
	for (i=0; step; step >>= 1)
		if (((i | step) <=n) && (aib_query(i | step) < val))
			i |= step;
	return i+1;
}

void solve()
{
	for (int i = 1; i<=n; i++)
		aib[i] = zeros(i);
	for (int i = n-1; i>=0; i--)
	{
		a[i] = binary_search(a[i]);
		aib_update(a[i],-1);
	}
}

int main ()
{
	read();
	solve();
	write();
	return 0;
}