Pagini recente » Cod sursa (job #2667327) | Cod sursa (job #369048) | Cod sursa (job #256858) | Cod sursa (job #1793019) | Cod sursa (job #3140556)
#include <fstream>
using namespace std;
ifstream cin ("schi.in");
ofstream cout ("schi.out");
int lungime , sir[30001] , clasament[30001] , aparitii[30001];
void Update (int indice)
{
while (indice <= lungime) {
aparitii[indice]++;
indice += (indice & -indice);
}
}
int Suma (int indice)
{
int suma = 0;
while (indice) {
suma += aparitii[indice];
indice -= (indice & -indice);
}
return suma;
}
int CautareBinara (int libere)
{
int stanga = libere + 1 , dreapta = lungime , pozitie = stanga;
while (stanga <= dreapta)
{
int mijloc = (stanga + dreapta) / 2 , ramase = mijloc - Suma(mijloc - 1) - 1;
if (ramase == libere)
{
if (!clasament[mijloc])
pozitie = mijloc , dreapta = stanga - 1;
else
stanga = mijloc + 1;
}
else
if (ramase > libere)
dreapta = mijloc - 1;
else
stanga = mijloc + 1;
}
return pozitie;
}
int main ()
{
cin >> lungime;
for (int indice = 1 ; indice <= lungime ; indice++)
cin >> sir[indice];
for (int indice = lungime ; indice ; indice--)
{
int pozitie = CautareBinara(sir[indice] - 1);
clasament[pozitie] = indice;
Update(pozitie);
}
for (int indice = 1 ; indice <= lungime ; indice++)
cout << clasament[indice] << '\n';
cout.close(); cin.close();
return 0;
}