Pagini recente » Cod sursa (job #1339955) | Cod sursa (job #2343767) | Cod sursa (job #2164167) | Cod sursa (job #34811) | Cod sursa (job #230506)
Cod sursa(job #230506)
#include <fstream>
#include <iostream>
using namespace std;
#define nmax 30001
int tree[nmax];
int v[nmax];
int sol[nmax];
int n;
void update(int idx, int val) {
while (idx <= n) {
tree[idx] += val;
idx += (idx & -idx);
}
}
int gt(int idx) {
int total = 0;
while (idx) {
total+= tree[idx];
idx -= (idx & -idx);
}
return total;
}
int main() {
ifstream fin("schi.in");
ofstream fout("schi.out");
fin >> n;
int i, j;
for (i = 1; i <= n; ++i) {fin >> v[i]; update(i, 1);}
for (i = n; i >= 1; --i) {
//find the v[i]th zero
int left = 1, right = n;
int sol2 = 0;
while (left <= right) {
int mid = (left + right) / 2;
int val = gt(mid);
if (val >= v[i]) {
if (val == v[i]) {if (sol2 == 0 || mid < sol2) sol2 = mid;}
right = mid - 1;
}
else left = mid + 1;
}
sol[sol2] = i;
update(sol2, -1);
}
for (i = 1; i <= n; ++i) {
fout << sol[i] << '\n';;
}
return 0;
}