Pagini recente » Cod sursa (job #1503286) | Cod sursa (job #733554) | Cod sursa (job #372438) | Cod sursa (job #1165494) | Cod sursa (job #3133134)
#include <iostream>
#include <fstream>
#define lsb(p) ((-p)&p)
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
int arb[30010], clasamentIntermediar[30010], clasamentFinal[30010], n;
void actualizare(int valoare, int pozitie) {
for (int i = pozitie; i <= n; i += lsb(i)) {
arb[i] += valoare;
}
}
int suma(int pozitie) {
int sum = 0;
for (int i = pozitie; i > 0; i -= lsb(i)) {
sum += arb[i];
}
return sum;
}
int cautareBinara(int x) {
int stanga = 1, dreapta = n, mijloc, val;
while (stanga <= dreapta) {
mijloc = (stanga + dreapta) / 2;
int aux = suma(mijloc);
if (aux == x) {
dreapta = mijloc - 1;
val = mijloc;
} else if (aux < x) {
stanga = mijloc + 1;
} else {
dreapta = mijloc - 1;
}
}
return val;
}
int main() {
f >> n;
for (int i = 1; i <= n; ++i) {
f >> clasamentIntermediar[i];
actualizare(1, i);
}
for (int i = n; i >= 1; --i) {
int aux = cautareBinara(clasamentIntermediar[i]);
clasamentFinal[aux] = i;
actualizare(-1, aux);
}
for (int i = 1; i <= n; ++i) {
g << clasamentFinal[i] << "\n";
}
f.close();
g.close();
return 0;
}