Pagini recente » Cod sursa (job #2228119) | Cod sursa (job #2232561) | Cod sursa (job #2327560) | Cod sursa (job #2060507) | Cod sursa (job #1355758)
#include <fstream>
#include <iostream>
using namespace std;
#define dim 30001
#define p2(x) ((x ^ (x - 1)) & x)
int n, i, pi, p;
int Arb[dim], a[dim], c[dim];
ifstream fin("schi.in");
ofstream fout("schi.out");
void Adauga(int p, int v) {
int i;
for (i = p; i <= n; i += p2(i))
Arb[i] += v;
}
int Suma(int p) { // suma pana la pozitia p
int i, s = 0;
for (i = p; i > 0; i -= p2(i))
s += Arb[i];
return s;
}
int Cauta(int v) {
int i, p = pi;
for (i = 0; p; p >>= 1)
if (i + p <= n)
if (Arb[i + p] < v) {
i += p, v -= Arb[i];
if (v == 0)
return i;
}
return i + 1;
}
int main() {
fin >> n;
for (i = 1; i <= n; i++) {
fin >> a[i];
Adauga(i, 1);
}
for (pi = 1; pi < n; pi <<= 1); // pasul initial pentru cautare
for (i = n; i >= 1; i--) {
p = Cauta(a[i]); // pozitia pana la care avem suma a[i]
c[p] = i; // concurentul i va fi pe pozitia p in clasamentul final
Adauga(p, -1);
/*
for (int j = 1; j <= n; j++) {
cout << Suma(j) - Suma(j - 1) << ' ';
}
cout << endl;*/
}
for (i = 1; i <= n; i++)
fout << c[i] << '\n';
}
/*
8
1
1
3
4
4
2
1
3
----------------
1
2 1
2 1 3
2 1 3 4
2 1 3 5 4
2 6 1 3 5 4
7 2 6 1 3 5 4
7 2 8 6 1 3 5 4
*/