Pagini recente » Cod sursa (job #141403) | Cod sursa (job #748850) | Cod sursa (job #2217965) | Cod sursa (job #3232888) | Cod sursa (job #2985171)
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");
int nrSchiori, pozitie[30005], fenwickTree[30005], schiori[30005];
int getLSB(int x)
{
return (x & (-x));
}
void update(int poz, int val)
{
for (; poz <= nrSchiori; poz += getLSB(poz))
fenwickTree[poz] += val;
}
int query(int poz)
{
int sum = 0;
for(; poz > 0; poz -= getLSB(poz))
sum += fenwickTree[poz];
return sum;
}
// Gasim al x-lea loc liber in clasament si il marcam ca ocupat
int rezolvare (int x)
{
// int pozitieInFenwick = 0, locuriLibereParcurse = 0;
// for (int i = log2(nrSchiori); i >= 0; i--)
// {
// int pozitiePosibila = pozitieInFenwick + (1 << i);
// if (fenwickTree[pozitiePosibila] == 0)
// continue;
// if (pozitiePosibila <= nrSchiori && fenwickTree[pozitiePosibila] <= x - locuriLibereParcurse)
// {
// pozitieInFenwick = pozitiePosibila;
// locuriLibereParcurse += fenwickTree[pozitieInFenwick];
// }
// }
// // Marcam pozitia din Fenwick ca fiind ocupata, asa ca anulam existenta locului disponibil
// update(pozitieInFenwick, -1);
// return pozitieInFenwick;
int st = 1, dr = nrSchiori, pozitieFenwick;
while (st <= dr)
{
int mid = (st + dr) / 2;
int locuriLibere = query(mid);
if (locuriLibere >= x)
pozitieFenwick = mid, dr = mid - 1;
else
st = mid + 1;
}
update(pozitieFenwick, -1);
return pozitieFenwick;
}
int main()
{
fin >> nrSchiori;
// Cream pozitiile in clasament pentru schiori
for (int i = 1; i <= nrSchiori; i++)
update(i, 1);
for (int i = 1; i <= nrSchiori; i++)
fin >> schiori[i];
for (int i = nrSchiori; i > 0; i--)
pozitie[rezolvare(schiori[i])] = i;
for (int i = 1; i <= nrSchiori; i++)
fout << pozitie[i] << "\n";
return 0;
}