Pagini recente » Cod sursa (job #2670108) | Cod sursa (job #2573662) | Cod sursa (job #3234408) | Cod sursa (job #2739264) | Cod sursa (job #1838717)
#include <fstream>
#include <algorithm>
using namespace std;
#define NMAX 30002
#define LSB(x) ( (x) & -(x) )
ifstream fin("schi.in");
ofstream fout("schi.out");
int N, v[NMAX], AIB[NMAX], Sol[NMAX];
bool Ocupat[NMAX];
// uodate pe pozitie
inline void AddVal(int pos, int val) {
for (int i = pos; i <= N; i += LSB(i))
AIB[i] += val;
}
// suma pe intervalul 1...pos
inline int GetSum(int pos) {
int res = 0;
for (int i = pos; i > 0; i -= LSB(i))
res += AIB[i];
return res;
}
int Bsearch(int val) {
int st = 1, dr = N;
while (st <= dr) {
int mid = (st + dr) >> 1;
int x = GetSum(mid);
if (x < val) {
st = mid + 1;
continue;
}
if (x > val) {
dr = mid - 1;
continue;
}
if (x == val) {
if (Ocupat[mid])
dr = mid - 1;
else
return mid;
}
}
}
int main() {
fin >> N;
//consider cate un schior pe fiecare pozitie
for (int i = 1; i <= N; ++i) {
fin >> v[i];
AddVal(i, 1);
}
// plec de la coada la cap, pentru ca asa am certitudine despre pozitia finala
for (int i = N; i >= 1; --i) {
int poz = Bsearch(v[i]); // caut binar a v[i] -a pozitie neocupata din clasament
Sol[poz] = i;
AddVal(poz, -1);
Ocupat[poz] = 1;
}
for (int i = 1; i <= N; ++i)
fout << Sol[i] << "\n";
return 0;
}