Pagini recente » Cod sursa (job #1922493) | Cod sursa (job #663408) | Cod sursa (job #1882898) | Cod sursa (job #223603) | Cod sursa (job #1991038)
#include <stdio.h>
#define MAX_N 30001
int n;
int crt_place[MAX_N];
int final_place[MAX_N];
int ftree[MAX_N];
void ftree_add(int pos, int val) {
while (pos <= n) {
ftree[pos] += val;
pos += pos & -pos;
}
}
int ftree_query(int pos) {
int sum = 0;
while (pos > 0) {
sum += ftree[pos];
pos -= pos & -pos;
}
return sum;
}
int bsearch(int val) {
int l = 1;
int h = n;
int mid;
while (l < h) {
mid = (l + h) >> 1;
if (ftree_query(mid) < val)
l = mid + 1;
else
h = mid;
}
return l;
}
int main(void) {
freopen("schi.in", "r", stdin);
freopen("schi.out", "w", stdout);
// read data and add 1 to all positions in ftree
// 1 means it's a free slot. 0 means it's been occupied
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &crt_place[i]);
ftree_add(i, 1);
}
// process the data beginning from the last skier. this last skier is
// certain of his final position. search for the k-th place and mark it
// as occupied. then repeat for remaining skiers.
int final_pos;
for (int i = n; i > 0; i--) {
// find the final place of skier i in the fenwick tree with bsearch
final_pos = bsearch(crt_place[i]);
final_place[final_pos] = i;
// make that position 0 (occupied)
ftree_add(final_pos, -1);
}
for (int i = 1; i <= n; i++) {
printf("%d\n", final_place[i]);
}
return 0;
}