Pagini recente » Cod sursa (job #874998) | Cod sursa (job #2999854) | Cod sursa (job #2189361) | Istoria paginii runda/aaaaaaaaaaaaaaaaaaaaaaa | Cod sursa (job #2791547)
#include <iostream>
#include <fstream>
#define inout(f) std::ifstream in((f) + (std::string) ".in");std::ofstream out((f) + (std::string) ".out")
#define d(x) std::cout << x << std::endl
#define dm(msg, x) std::cout << msg << x << std::endl
const int NMAX = 3e4;
const int LOGMAX = 15;
int n, logN;
int queries[1 + NMAX];
int ans[1 + NMAX];
int biTree[2 * NMAX];
inline int bsLog2(int a) {
int left = 0, right = LOGMAX, ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if ((1 << mid) <= a) {
ans = mid;
left = mid + 1;
}
else
right = mid - 1;
}
return ans;
}
inline int lsb(int a) {
return a & -a;
}
void biTreeUpdate(int index, int value) {
for (int i = index; i <= n; i += lsb(i))
biTree[i] += value;
}
int biTreeQuery(int index) {
int ans = 0;
for (int i = index; i > 0; i -= lsb(i))
ans += biTree[i];
return ans;
}
// int biTreeSearch(int target) {
// int index = 0, ans = -1;
// for (int exp = logN; exp >= 0; --exp) {
// if (biTree[index + (1 << exp)] < target)
// index += (1 << exp), target -= biTree[index];
// else if (biTree[index + (1 << exp)] == target)
// ans = index + (1 << exp);
// }
// return ans;
// }
int biTreeSearch(int target) {
int left = 1, right = n;
int ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (biTreeQuery(mid) >= target)
ans = mid, right = mid - 1;
else
left = mid + 1;
}
return ans;
}
int main() {
inout("schi");
in >> n;
logN = bsLog2(n);
for (int i = 1; i <= n; ++i) {
in >> queries[i];
biTreeUpdate(i, 1);
}
for (int i = n; i >= 1; --i) {
int index = biTreeSearch(queries[i]);
ans[index] = i;
biTreeUpdate(index, -1);
}
for (int i = 1; i <= n; ++i)
out << ans[i] << '\n';
return 0;
}