Pagini recente » Cod sursa (job #2005860) | Cod sursa (job #1754844) | Cod sursa (job #203376) | Cod sursa (job #867054) | Cod sursa (job #3208071)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
const string fileName = "schi";
ifstream in (fileName + ".in");
ofstream out (fileName + ".out");
int n;
int aib[4 * 30000 + 1];
int v[30000];
int ans[30000];
/** Ideea: aib pentru suma totala
* nup
* Ideea: aib cu cautare binara
*
*
*/
int lPoz(int poz){
return poz * 2;
}
int rPoz(int poz){
return poz * 2 + 1;
}
void update(int poz, int val){
int l, r, nr = 1; ///nr = pozitia in aib, poz = pozitia in v
l = 1; r = n;
int mid = (r + l) / 2;
while(l <= r && l != r){
mid = (r + l) / 2;
if(mid < poz){
nr = rPoz(nr);
l = mid + 1;
}
else{
r = mid;
nr = lPoz(nr);
}
}
aib[nr] = val;
while(nr){
aib[nr / 2] = aib[lPoz(nr / 2)] + aib[rPoz(nr / 2)];
nr /= 2;
}
}
int query(int nr){
int l, r, poz;
poz = 1; ///incepem cu varful aib-ului
l = 1; r = n;
int mij = (l + r) / 2;
while(l < r){
mij = (l + r) / 2;
if(aib[lPoz(poz)] < nr){
nr -= aib[lPoz(poz)];
poz = rPoz(poz);
l = mij + 1;
}
else{
poz = lPoz(poz);
r = mij;
}
}
return l;
}
int main()
{
in >> n;
for(int i = 1; i <= n; i ++){
in >> v[i];
update(i, 1);
}
for(int i = n; i >= 1; i --){
ans[query(v[i])] = i;
update(query(v[i]), 0);
}
for(int i = 1; i <= n; i ++){
out << ans[i] << endl;
}
return 0;
}