Cod sursa(job #3134697)

Utilizator DenisaCrCranganu Denisa Mariana DenisaCr Data 30 mai 2023 13:50:06
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");

const int N = 30005;

int n; // numarul de elemente
int arbore[4 * N], loc[N], clasament[N];    // arborele

void build(int tl = 1, int tr = n, int node = 1) // functia construieste arborele
{
	if (tl == tr)
	{
		arbore[node] = 1; // initializam valorile
		return;
	}

	int mid = (tl + tr) / 2; // mijlocul intervalului

	build(tl, mid, node * 2); // construim arborele din stanga
	build(mid + 1, tr, node * 2 + 1); // construim arborele din dreapta
	arbore[node] = arbore[node * 2] + arbore[node * 2 + 1]; // calculam nodul
}

int getPlace(int val, int tl = 1, int tr = n, int node = 1) // functia returneaza locul pe care trebuie sa il ocupe valoarea val
{
	arbore[node]--; // scadem valoarea din nod

	if (tl == tr)
	{
		return tl;
	}

	int mid = (tl + tr) / 2; // mijlocul intervalului

	if (val <= arbore[node * 2]) // daca valoarea se afla in stanga
	{
		return getPlace(val, tl, mid, node * 2);
	}
	else
	{
		return getPlace(val - arbore[node * 2], mid + 1, tr, node * 2 + 1); // daca valoarea se afla in dreapta
	}
}

int main()
{
	f >> n;

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

	build();

	for (int i = n; i >= 1; i--)
	{
		clasament[getPlace(loc[i])] = i;
	}

	for (int i = 1; i <= n; i++)
	{
		g << clasament[i] << '\n';
	}
}