Pagini recente » Cod sursa (job #619591) | Cod sursa (job #3156902) | Cod sursa (job #1810822) | Cod sursa (job #2602519) | Cod sursa (job #3134697)
#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';
}
}