Cod sursa(job #1760142)

Utilizator ArkinyStoica Alex Arkiny Data 20 septembrie 2016 13:22:50
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#include<algorithm>
using namespace std;

int N;

int AIB[35000];
int h[35000];
int v[35000];
int rez[35000];
ifstream in("schi.in");
ofstream out("schi.out");

void update(int AIB[],int x,int val)
{
	for (;x <= N;x += (x&(-x)))
		AIB[x] += val;
}

int query(int AIB[],int x)
{
	int e = 0;
	for (;x;x -= (x&(-x)))
		e += AIB[x];

	return e;
}

int main()
{
	in >> N;


	for (int i = 1;i <= N;++i)
	{
		in >> v[i];
		update(AIB,i,1);
	}
	

	for (int i = N;i >= 1;--i)
	{
		int l = 1, r = N;
		int poz=0;
		while (l <= r)
		{
			int mid = (l + r) / 2;

			int e = query(AIB, mid);
			if (e == v[i])
				poz = mid, r = mid - 1;
			else if (e > v[i])
				r = mid - 1;
			else
				l = mid + 1;

		}
		rez[poz] = i;
		update(AIB, poz, -1);

	}

	for (int i = 1;i <= N;++i)
		out << rez[i] << '\n';


	return 0;
}