Cod sursa(job #2437935)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 10 iulie 2019 19:21:05
Problema Schi Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");

const int nmax = 30006;
int n, v[nmax], aib[nmax], vrasp[nmax];

int zeros(int x)
{
	return (x ^ (x - 1))&x;
}

void add(int x)
{
	for(int i = x; i<=n; i+=zeros(i))
		aib[i]++;
}

int calc(int x)
{
	int rez = 0;
	for(int i = x; i>0; i-=zeros(i))
		rez += aib[i];
	return rez;
}

int bs(int x)
{
	int lo = 0, hi = n + 1, mid;
	while(hi - lo>1)
	{
		mid = (hi + lo) / 2;
		int already_filled = calc(mid);

		if(mid - already_filled==x && mid - 1 - calc(mid - 1)!=x)
			return mid;

		if(mid - already_filled>=x)
			hi = mid;
		else
			lo = mid;
	}

	if(lo - calc(lo)==x && lo - 1 - calc(lo - 1)!=x)
			return lo;
	if(hi - calc(hi)==x && hi - 1 - calc(hi - 1)!=x)
			return hi;

	return -1;

}

int main(){
	int player_unu=0;

	in>>n;
	for(int i = 1; i<=n; i++)
	{
		in>>v[i];
	}

	for(int i = n; i>0; i--)
	{
		int pozitie = bs(v[i]);
		vrasp[pozitie] = i;
		add(pozitie);
	}

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

	return player_unu;
}