Cod sursa(job #2312046)

Utilizator richard26Francu Richard richard26 Data 4 ianuarie 2019 01:00:34
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

int aib[30010], v[30010];
int n;

void update(int poz, int val)
{
	for (int i = poz; i <= n; i += (i & -i))
		aib[i] += val;
}

int sum(int poz)
{
	int s = 0, i;
	for (i = poz; i >= 1; i -= (i & -i))
		s += aib[i];

	return s;
}

int caut(int st, int dr, int p)
{
	int val, mij, poz;
	while(st <= dr)
	{
		mij = (st + dr) / 2;
		val = sum(mij);
		if(val >= v[p])
		{
			poz = mij;
			dr = mij - 1;
		}
		else
		{
			st = mij + 1;
		}
	}
	return poz;
}
int final[30010];
int main()
{
	ifstream f("schi.in");
	ofstream g("schi.out");
	f>>n;
//	cout<<n;
	int i, p;
//	g<<"3";
	for (i = 1; i <= n; i++)
	{
		f>>v[i];
		update(i, 1);
	}
//		g<<"3";
	for (i = n; i >=1; i--)
	{
		p = caut(1, n, i);
		final[p] = i;
		update(p, -1);
	}

	for(i = 1; i<= n; i++)
	{
		g<<final[i]<<"\n";
	}
	return 0;
}